Temas:
| Ejemplo | Significado | Declaración |
|---|---|---|
| Map m= new Map(); | Construye un arreglo asociativo con llaves enteras, inicialmente vacío | Map() |
| m.put(2, "hola"); | Asocia el entero 2 con el string "hola" | void put(int ll, Object v) |
| String s= (String)m.get(2); | entrega el objeto asociado a la llave 2 ("hola"). Si la llave no posee valor asociado se produce un error. | Object get(int ll) |
| if (m.isMapped(2)) ... | entrega verdadero si la llave 2 tiene un valor asociado. | boolean isMapped(int ll) |
| m.remove(2) | elimina la asociación (2,...) del arreglo asociativo. | void remove(int ll) |
Por simplicidad, esta versión restringida de Map no acepta establecer asociaciones entre enteros y otros enteros o números reales, como:
m.put(1, 3); // no implementada
m.put(1, 3.14); // no implementada
En la figura se observa la estructura de una arreglo asociativo que posee las asociaciones (2, "hola"), (5, "que") y (3, "tal").
En el objeto que representa el arreglo asociativo se coloca una referencia del primer eslabón de la lista enlazada. Por conveniencia, se incluye un eslabón falso para que la lista nunca esté vacía. En este caso no es útil tener una referencia del último eslabón, porque ninguna operación requiere agregar algún eslabón al final de la lista enlazada.
Observe que el orden en que se organiza la lista enlazada es irrelevante. El eslabón que contiene la llave 2 podría haber quedado perfectamente después del eslabón de la llave 5 sin alterar el contenido formal del arreglo asociativo. El orden en que quedarán almacenadas las llaves depende únicamente del orden en que se hagan las asociaciones.
Por lo tanto, la estructura de representación de la clase Map y la clase EslabónM es la siguiente:
class Map extends Program {
EslabonM primero= new EslabonM(0, null, null);
... la implementación de la operaciones de Map ...
}
class EslabonM {
int llave;
Object valObj;
EslabonM proximo;
EslabomM(int llave, Object valObj, EslabomM proximo) {
this.llave= llave;
this.valObj= valObj;
this.proximo= proximo;
}
}
Object get(int llave) {
EslabonM e= primero.proximo;
while (e!=null) {
if (e.llave==llave)
return e.valObj;
e= e.proximo;
}
fatalError("No se encontro la llave "+i); // termina la ejecución!
return null; // para que pase la compilacion
}
También se necesita hacer este mismo recorrido con la operación put. Si la llave existe se modifica el valor en el mismo eslabón. Si la llave no existía previamente en la lista enlazada, se crea un nuevo eslabón para esa llave y se agrega por conveniencia justo después del eslabón falso:
void put(int llave, Object valObj) {
EslabonM e= primero.proximo;
while (e!=null) {
if (e.llave==llave) { // la llave existe
e.valObj= valObj; // cambiamos su valor
return; // y retornamos
}
e= e.proximo;
}
// la llave no existía previamente
// Creamos un nuevo eslabon y lo agregamos entre el eslabon
// falso y el segundo eslabon
e= new EslabonM(llave, valObj, primero.proximo);
primero.proximo= e;
}
Ejercicio: Verifique que las dos operaciones funcionan correctamente cuando el arreglo asociativo se encuentra vacío (cuando la lista enlazada sólo contiene el eslabón falso).
El primer intento de implementación que viene a la mente consiste en usar el patrón de recorrido de los eslabones para buscar la llave que se desea eliminar. Sin embargo, este patrón no sirve porque cuando se encuentre la llave, la variable de instancia prox que hay que modificar se encuentra en el eslabón visitado en la iteración anterior. Pero este eslabón ya se visitó y no es posible volverlo a recorrer si comenzar por el primer eslabón.
Para resolver el problema, modificamos ligeramente el patrón de recorrido de modo de mantener en la variable anterior el eslabón visitado en la iteración anterior. La siguiente figura muestra cómo realizar la eliminación del eslabón utilizando la variable anterior:
El código para eliminar una llave del arreglo asociativo es entonces:
void remove(int llave) {
EslabonM anterior= primero;
EslabonM proximo= primer.proximo;
while (proximo!=null && proximo.llave!=llave) {
anterior= proximo;
proximo= proximo.proximo;
}
if (proximo==null) // la llave no existe en el arreglo asociativo
return;
// la llave si existe, por lo que se elimina el eslabon
// referenciado por proximo
anterior.proximo= proximo.proximo;
}
Observe que construir un arreglo asociativo de n llaves toma tiempo O(n*n), lo que sabemos es muy ineficiente de acuerdo a lo estudiado con los algoritmos de ordenamiento.
En la próxima clase veremos una implementación eficiente de un arreglo asociativo que permite construir un arreglo con n asociaciones en tiempo O(n*log n) en el caso promedio. Esta implementación estará basada en un nueva estructura de datos: el árbol de búsqueda binaria.
Resumen
Todas las operaciones que hemos realizado con listas enlazadas se pueden resumir en los siguientes patrones de programación:
