Lunes 24 de Mayo

Búsqueda en Arreglos

Objetivos:

Temas:


Búsqueda del mínimo/máximo

Un problema frecuente al trabajar con arreglos consiste en encontrar el mínimo/máximo valor en el arreglo. Por ejemplo, supongamos que el arreglo tabNotas contiene notas de alumnos en un control. Las llaves varían entre 1 y n. El siguiente programa encuentra el máximo y el mínimo:

    int i=1;
    double min= 7.1;
    double max= 0.0;
    while (i<=n) {
      double nota= tabNotas.getDouble(i);
      if (nota<min)
        min= nota;
      if (nota>max)
        max= nota;
      i= i+1;
    }
Observe que si el arreglo está vacío (n es 0), entonces al final del ciclo min es 7.1 y max es 0.0. Como estas notas no son válidas, se puede consultar por estos valores para determinar a posteriori que el arreglo estaba vacío.

Sin embargo, en el caso general no se conoce el rango que pueden tomar los valores en el arreglo. El siguiente patrón de programación se puede usar cuando se conoce que el arreglo tiene al menos un elemento:

    int llave= segunda llave;
    Tipo max= arreglo.getTipo(primera llave);
    while (llave<=última llave) {
      ...
      if (arreglo.getTipo(llave) > max)
         max= arreglo.getTipo(llave);
      ...
    }
No siempre lo único que se necesita es el valor del máximo. En ocasiones, también se necesita la posición del máximo en el arreglo (la llave):

    int llave= primera llave;
    Tipo max= arreglo.getTipo(primera llave);
    int llaveMax= primera llave;
    while (llave<=última llave) {
      ...
      if (arreglo.getTipo(llave) > max) {
         max= arreglo.getTipo(llave);
         llaveMax= llave;
      }
      ...
    }
Al final del ciclo, la variable llaveMax contiene la posición del máximo en el arreglo.


Búsqueda por contenido

Otro problema frecuente al trabajar con arreglos consiste en encontrar la llave cuyo valor asociado es un valor predeterminado. Por ejemplo, supongamos que el arreglo tabNombres contiene nombres (strings) de alumnos en un control. Las llaves varían entre 1 y n. El siguiente programa encuentra la llave i, tal que su valor asociado es nombre:

    String nombre= ...;
    int i=1;
    while (i<n) {
      if (compare(tabNombres.getString(i),nombre)==0)
        break;
      i= i+1;
    }
    if (i<=n)
      ... // el nombre se encuentra en la posicion i
    else
      ... // el nombre no se encuentra en el arreglo
Esta búsqueda se escribe más elegantemente mediante:

    String nombre= ...;
    int i=1;
    while (i<n && compare(tabNombres.getString(i),nombre)!=0)
      i= i+1;
    if (i<=n)
      ... // el nombre se encuentra en la posicion i
    else
      ... // el nombre no se encuentra en el arreglo
Este último es un patrón muy utilizado en los problemas de búsqueda por contenido.

Ejercicio:

El arreglo tabNombres contiene nombres de alumnos, el arreglo tabNotas contiene sus notas en un control. Escriba un programa que entable el siguiente diálogo con el usuario:

    Nombre ? Gloria Hernandez
    Su nota es 6.0
    Nombre ? Juan Perez
    Su nota es 5.5
    Nombre ? Pablo Neruda
    No se encontro este alumno
    ...
    Nombre ? fin
    Fin.

Arreglos con llaves de tipo string

En los arreglos de la clase Map, los valores pueden ser enteros, reales, strings o booleans. Pero las llaves sólo pueden ser valores enteros. A continuación examinaremos la clase StringMap, que permite construir arreglos que usan llaves de tipo String.

Motivación: el archivo "votos.txt" contiene los resultados de una elección en el siguiente formato.

    Juan
    Pedro
    Juan
    Patricia
    Patricia
    ...
Los candidatos a la elección son Juan, Patricia, Pedro y Mónica. Escribir un programa que haga el recuento de votos.

Solución cómoda: Usar un arreglo asociativo con llaves de tipo string.

    MapString tab= new MapString();
    tab.put("Juan", 0);
    tab.put("Patricia", 0);
    tab.put("Pedro", 0);
    tab.put("Monica", 0);
    TextReader lect= new TextReader("votos.txt");
    while (true) {
      String cand= lect.readLine();
      if (lect.eofReached())
        break;
      tab.put(cand, tab.getInt(cand)+1);
    }
    lect.close();
    println("Juan : "+tab.getInt("Juan")+" votos");
    println("Patricia : "+tab.getInt("Patricia")+" votos");
    println("Pedro : "+tab.getInt("Pedro")+" votos");
    println("Monica : "+tab.getInt("Monica")+" votos");
Los arreglos asociativos de la clase MapString son similares a los de la clase Map. Las operaciones son las mismas, pero difieren en el tipo de la llave: strings para un MapString y enteros para un Map.


Ejercicio::

Resuelva nuevamente el problema que indica la nota de un alumno. Esta vez, antes de comenzar el diálogo con el usuario, construya un arreglo que dado el nombre de un alumno, le asocie su nota. Luego, consulte este arreglo para determinar la nota de un alumno.

Utilice el método booleano tab.isMapped(nombre) para determinar si la llave nombre posee o no un valor asociado en la tabla tab.