Estructuras Datos Java
Estructuras Datos Java
9 786070 227035
AMPARO LÓPEZ GAONA
FACULTAD DE CIENCIAS
2011
López Gaona, Amparo
Estructuras de datos con Java : un enfoque práctico / Amparo
López Gaona. -- México : UNAM, Facultad de Ciencias, 2011.
xi, 222 p. ; 23.5 cm. -- (Las prensas de ciencias) (Temas de
computación)
Incluye índice
Bibliografía: p. 219
ISBN 978-607-02-2703-5
ISBN: 978-607-02-2703-5
Agradezco a todas las personas que colaboraron, de una o de otra forma, en la materializa-
ción de este proyecto. Especialmente a Salvador por el realizar el trabajo relacionado con la
tipografı́a del libro y por su invaluable ayuda durante la etapa final del desarrollo del mismo
en que me vı́ forzada a ser zurda y él se convirtió en mucho más que “mi mano derecha”.
También agradezco a Andrea por su ayuda, apoyo, compañı́a y ser mi chofer durante mi
zurdera, además de animarme durante mi rehabilitación.
La imagen que aparece en esta página es una “colección de objetos” realizada por Andrea
en cuarto año de primaria.
Índice general
Introducción ix
2 Listas 33
2.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2. El TAD Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3. Aplicaciones de listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3.1. Lista de identificadores . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.2. Orden en recipientes . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.3.3. Problema de José . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4. Implementación de listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.4.1. Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.4.2. Listas ligadas con una referencia al nodo final . . . . . . . . . . . . . 51
2.4.3. Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3 Pilas 59
3.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.2. El TAD Pila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.3. Aplicaciones de pilas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
i
ii ÍNDICE GENERAL
4 Colas 83
4.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.2. El TAD Cola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.3. Aplicaciones de colas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.3.1. Uso en sistemas operativos . . . . . . . . . . . . . . . . . . . . . . . . 85
4.3.2. Acomodo de trenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.3.3. Salida rápida de laberintos . . . . . . . . . . . . . . . . . . . . . . . . 92
4.4. Implementación del TAD Cola . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5 Árboles 105
5.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.2. Árboles binarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.3. Implementación de árboles binarios . . . . . . . . . . . . . . . . . . . . . . . 108
5.3.1. Recorridos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.4. Aplicaciones de árboles binarios . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.4.1. Árbol para expresiones aritméticas . . . . . . . . . . . . . . . . . . . 112
5.4.2. Juego de adivinar animales . . . . . . . . . . . . . . . . . . . . . . . . 115
5.5. Árboles binarios de búsqueda . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.5.1. Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.5.2. Aplicación de árboles binarios de búsqueda . . . . . . . . . . . . . . . 127
5.6. Árboles balanceados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.7. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
A Recursión 199
A.1. Búsqueda con retroceso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
Bibliografı́a 219
v
vi ÍNDICE DE FIGURAS
vii
Introducción
ix
x CAPÍTULO 0. INTRODUCCIÓN
Capı́tulo 2. Listas. Las listas son estructuras de datos sencillas que no imponen restriccio-
nes al contenido ni a la forma de acceder a los elementos que contienen, es decir pueden
contener datos de cualquier tipo, con repetición o no, y no necesariamente ordenados.
Capı́tulo 3. Pilas. Una pila es una estructura de datos cuya única restricción está en la
forma de acceder a los elementos almacenados en ella, ya que tanto la entrada como la
salida de los datos es por un sólo lugar. Aunque parece ser una restricción muy fuerte,
esta estructura es muy sencilla de implementar y sumamente útil en aplicaciones en
las que se requiere que los datos se recuperen en orden inverso a como se almacenan.
Capı́tulo 4. Colas. Una cola es una estructura de datos que almacena una colección de
elementos sin restricción en cuanto al valor de los mismos, con o sin repetición. Sin
embargo, el acceso a los datos está restringido al permitir que se inserten siempre por
la parte trasera de la cola y se eliminen por el frente de la misma. Con ello se consigue
que los datos salgan en el mismo orden en que entran.
Capı́tulo 5. Árboles. Un árbol es una estructura de datos que impone un orden jerárquico
a los datos. Existen diferentes tipos de árboles en este capı́tulo se presentan los árboles
en general, los árboles binarios, y dentro de éstos, los árboles de búsqueda y los balan-
ceados. Algunas de las aplicaciones presentadas en este capı́tulo no sólo requieren de
árboles, sino de otras estructuras de datos de las presentadas en capı́tulos anteriores.
xi
Apéndice C. Normas de estilo de Java. Este apéndice contiene las principales guı́as de
estilo para organizar y dar formato al código fuente de los programas en Java.
1.1. Introducción
Los lenguajes de programación proporcionan tipos de datos llamados primitivos, los cuales
pueden ser utilizados por los programadores para definir las variables requeridas en la solución
de su problema. Cada tipo de dato es una abstracción que determina el conjunto de valores
que deben tener los datos, ası́ como las operaciones que pueden realizarse con ellos y las
restricciones o propiedades de las operaciones.
Los tipos de datos primitivos proporcionados en Java son boolean, byte, short, int,
long, float, double y char. A manera de ejemplo se tiene que el tipo de datos boolean
sólo tiene dos posibles valores: true y false, y define para él las operaciones de conjunción,
disyunción y negación. Una caracterı́stica o restricción de estas operaciones es que el resultado
es también un valor booleano. Java es un lenguaje en el cual todo dato debe tener un tipo
asociado antes de poder usarse; este aspecto tiene la ventaja de que es posible detectar alguna
inconsistencia entre el tipo de los operandos utilizados en las operaciones para cada tipo de
datos.
Aunque los datos de tipo primitivo son ampliamente utilizados es frecuente que en las
aplicaciones se requiera trabajar con datos de tipos particulares. Por ejemplo, se podrı́a
estar desarrollando un programa que manipula figuras geométricas y por lo tanto se requiera
constantemente trabajar con puntos en el plano cartesiano, entonces resulta más cómodo
para el programador, y más legible, trabajar con datos del tipo Punto y no con números.
1
2 CAPÍTULO 1. TIPOS ABSTRACTOS DE DATOS
El concepto de tipo abstracto de datos (TAD) generaliza la noción de tipos de datos pro-
porcionados por el lenguaje de programación al permitir que el programador cree sus propios
tipos de datos, especificando los componentes del dato y las operaciones sobre datos de ese
nuevo tipo. Se denominan TAD porque nada en la definición indica cómo se implementan las
operaciones, por tanto, puede haber más de una implementación para cada TAD. Ejemplos
de TAD pueden ser el tipo Punto, Racional, Alumno, Fecha.
Una estructura de datos es una forma de organizar conjuntos de datos, generalmente del
mismo tipo, con el objetivo de facilitar la manipulación de tales datos en forma individual o
colectiva. En este documento se presentan las estructuras de datos como tipos abstractos de
datos debido a que se puede definir cada uno vı́a una interfaz e implementarse en una clase
independiente. El usuario sólo sabe qué operaciones puede realizar con cada TAD y cómo
usarlas, sin importar la implementación de las mismas.
import java.io.*;
import java.util.*;
/**
* Programa que determina las palabras que están en un texto dado y no
* están en un diccionario.
* @author Amparo López Gaona
* @version Abril 2011
*/
public class VerificadorSintaxis {
private static Conjunto leerPalabras(Reader in, int n) throws IOException{
Conjunto resultado = new Conjunto(n); // Conjunto para n palabras máximo
StreamTokenizer tok = new StreamTokenizer(in);
tok.ordinaryChar(’.’);
tok.lowerCaseMode(true);
int c = tok.nextToken();
while (c != StreamTokenizer.TT_EOF) {
if (c == StreamTokenizer.TT_WORD) {
resultado.agregar(tok.sval);
}
c = tok.nextToken();
}
return resultado;
}
El arreglo de datos contiene a los elementos del conjunto; es importante notar que no se ha
definido el tamaño del arreglo, pues es desconocido hasta su creación. En la implementación
se presentan tres constructores: uno por omisión, otro de copia y otro que recibe el tamaño
del conjunto.
Método 1.1. Constructor por omisión. Este constructor crea un conjunto con capacidad
para 20 elementos. Es preciso recordar que la instrucción this llama al constructor de esta
clase cuya firma coincida con el tipo y cantidad de parámetros en this.
/**
* Constructor de un conjunto con capacidad para 20 elementos.
*/
public Conjunto() {
this(20);
}
Método 1.2. Constructor que recibe un número entero que especifica la cantidad de datos
permitidos en el conjunto. Si la cantidad que recibe el constructor no es válida crea un con-
junto con capacidad para 20 datos. El arreglo se llena con el valor null para especificar que en
cada localidad no se tiene almacenado ningún valor válido, con lo cual esta implementación
impone la restricción de que ningún conjunto puede tener a null como elemento.
/**
* Constructor de un conjunto con capacidad para los elementos
* indicados. Si el tama~
no es negativo o cero, se construye un
* conjunto con capacidad para 20 elementos.
* @param tam capacidad del conjunto.
*/
public Conjunto(int tam) {
datos = new Object[tam <= 0 ? 20 : tam];
for (int i = 0; i < datos.length; i++)
datos[i] = null;
}
Método 1.3. Constructor de copia. Como su nombre indica hace una copia del conjunto
que recibe como parámetro.
/**
* Constructor de copia.
* @param Conjunto -- conjunto que se tomará como valor inicial para
* crear el nuevo.
*/
public Conjunto(Conjunto c) {
1.4. IMPLEMENTACIÓN DE CONJUNTOS 7
Método 1.4. Método para determinar si un conjunto no tiene elementos. Para ello, en el
método se recorre todo el arreglo buscando que todos los elementos sean igual a null, en
cuyo caso devuelve true. Si algún elemento es null devuelve false.
/**
* Determina si el conjunto tiene elementos o no.
* @return boolean - Devuelve true si el conjunto no tiene elementos y
* false en otro caso.
*/
public boolean estaVacio(){
for (int i = 0; i < datos.length; i++)
if (datos[i] != null) return false;
return true;
}
Método 1.5. Método para calcular la cantidad de elementos en el conjunto, para ello lo
recorre contando los elementos diferentes de null.
/**
* Devuelve la cantidad de elementos que tiene el conjunto.
* @return int - cantidad de elementos que tiene el conjunto.
*/
public int tamanio(){
int tam = 0;
for (int i = 0; i < datos.length; i++)
if (datos[i] != null) tam++;
return tam;
}
Método 1.6. Método para dejar vacı́o un conjunto sustituyendo todos sus elementos por el
valor null.
/**
* Elimina los elementos que tiene el conjunto.
*/
public void vaciar(){
for (int i = 0; i < datos.length; i++)
datos[i] = null;
}
8 CAPÍTULO 1. TIPOS ABSTRACTOS DE DATOS
Método 1.7. Método para determinar si un elemento dado está en el conjunto. Para ello
recorre el arreglo buscando el elemento mediante el uso del método equals. Una buena
costumbre es la de sobre-escribir en todas las clases el método equals para poder comparar
objetos de la misma clase por su estado y no por su referencia.
/**
* Determina si un elemento está contenido en el conjunto.
* @param elem - elemento que se desea saber si está en el conjunto.
* @return boolean - devuelve true si el elemento está en el conjunto y
* false en otro caso.
*/
public boolean contiene (Object elemento){
if (!estaVacio())
for (int i = 0; i < datos.length; i++)
if (elemento.equals(datos[i]))
return true;
return false;
}
Método 1.8. Método para eliminar del conjunto el elemento indicado; para hacerlo lo
sustituye por el valor null, que se sabe es un elemento que no está contenido en el conjunto.
Si el elemento no está en el conjunto no hace nada pues el objetivo es que ese elemento no
esté en el conjunto.
/**
* Elimina del conjunto el elemento especificado.
* @param elem - elemento que se desea eliminar del conjunto.
*/
public void eliminar(Object elemento) {
if (!estaVacio())
for (int i = 0; i < datos.length; i++)
if (elemento.equals(datos[i])) {
datos[i] = null;
return;
}
}
Método 1.9. Método para agregar un elemento al conjunto. Para ello se busca el pri-
mer lugar desocupado y si el elemento no está en el conjunto se inserta. Si el elemento ya
está en el conjunto no hace nada, y si el conjunto ya no tiene espacio se dispara la excepción
IllegalArgumentException.
1.5. ITERADORES 9
/**
* Agrega un elemento al conjunto, siempre y cuando no exista.
* @param elem - Elemento a insertar.
* @throws IllegalArgumentException - cuando el conjunto está lleno.
*/
public void agregar(Object elemento){
if (! contiene(elemento)) {
for (int i=0; i < datos.length; i++)
if (datos[i] == null) {
datos[i] = elemento;
return;
}
throw new IllegalArgumentException("El conjunto está lleno.");
}
}
Es necesario notar que al agregar un nuevo elemento no se asigna una copia de él, debido
a que se desconoce la clase del mismo. Esto puede ser un problema, por ejemplo, si se tiene
un conjunto con las personas que viven en una ciudad y por cualquier causa se actualiza
el domicilio de alguna persona a través de los métodos que se tengan para ello en la clase
Persona, de manera automática e implı́cita se actualiza en el conjunto y podrı́a darse el
caso de que esta actualización dé lugar a que el objeto modificado ya no cumpla con algún
criterio que le permitió ser parte del conjunto, pero como ya es parte de él la situación pasa
inadvertida. Para evitar este problema es conveniente que al llamar al método agregar en
el parámetro se asigne una copia del objeto que se desea agregar no el objeto mismo. Para
ello se puede utilizar el constructor de copia o bien el método clone especificados en la clase
del objeto.
En la siguiente sección se presenta un concepto de gran ayuda en la programación en
general, pero muy útil en la programación de los métodos restantes (unión, intersección,
etcétera) de la interfaz Conjuntable.
1.5. Iteradores
Una tarea frecuente al trabajar con una colección o estructura de datos es recorrerla para
obtener todos los elementos que la componen, ya sea para imprimirlos o bien realizar una
operación con todos ellos. Por ejemplo, incrementar el salario de todos los empleados, dar
de alta un conjunto de alumnos en un curso particular, etcétera.
Para ejemplificar esta situación se puede suponer que se requiere escribir un programa en
el que es necesario imprimir el contenido de un conjunto.
Ejemplo 1.2. Primera versión de un programa que imprime el contenido de un conjunto.
10 CAPÍTULO 1. TIPOS ABSTRACTOS DE DATOS
Esta es una forma sencilla de imprimir los elementos del conjunto, sin embargo, en el
caso de la implementación para conjuntos que se presentó en la sección anterior no es posible
hacerlo porque no se tiene el método obtenerElemento. Aun si se tuviera no serı́a apropiado
especificar la posición del elemento, porque eso va contra la definición de conjunto, en tanto
que los datos no se guardan por posición.
Una posibilidad es incluir en la clase Conjunto un método obtenerElementos (método
1.10) que devuelva el arreglo en donde está almacenado el conjunto.
Método 1.10. Método que devuelve el arreglo en donde se guarda un conjunto.
• next devuelve el siguiente elemento de la colección. La primera vez que se llama a este
método devuelve el primer elemento de la colección. Si la colección no tiene elementos
y se llama a este método, se dispara la excepción NoSuchElementException.
Normalmente las clases que implementan o tienen colecciones incluyen un método que
devuelve un iterador. En general, el iterador se implementa en una clase interna privada
debido a que ésta tiene acceso, sin calificativo, a todos los métodos y estructura del objeto
que la encierra, independientemente de la visibilidad de éstos afuera de la clase.
Clase 1.2. Clase Conjunto que incluye la implementación de un iterador.1
import java.util.Iterator;
/**
* Método que devuelve un iterador sobre el conjunto
* @return Iterator -- iterador sobre el conjunto
1
En la interfaz Conjuntable no se especificó el iterador por cuestiones didácticas, sin embargo es conve-
niente incluir la firma del método que devuelve el iterador.
12 CAPÍTULO 1. TIPOS ABSTRACTOS DE DATOS
/* Operación no implementada */
public void remove() throws UnsupportedOperationException,
IllegalStateException {
throw new UnsupportedOperationException();
}
}
}
Como puede observarse, la implementación del iterador depende por completo de la im-
plementación del conjunto, sin embargo para su utilización ya no se requiere conocer la
implementación de éste, sólo basta conocer los métodos del iterador.
Método 1.11. En el siguiente ejemplo se muestra la forma de utilizar el iterador para
imprimir todos los elementos del conjunto. Para que el método muestre adecuadamente los
elementos del conjunto, en la clase de estos elementos se debe tener el método toString.
1.5. ITERADORES 13
/**
* Método para imprimir los elementos de un conjunto
* @param Conjunto - Conjunto que se desea imprimir
*/
public void imprimir(Conjunto c) {
Iterator it = c.iterador();
while (it.hasNext())
System.out.print(it.next() + " ");
}
/**
* Método que devuelve la unión de dos conjuntos
* @param Conjunto -- conjunto que unirá al que llama a este método
* @return Conjunto -- conjunto con la unión
*/
public Conjunto union(Conjuntable c) {
Conjunto cUnion = new Conjunto(this);
Iterator it = c.iterador();
while(it.hasNext()) {
cUnion.agregar(it.next());
}
return cUnion;
}
Método 1.13. El método que calcula la intersección de dos conjuntos utiliza un iterador
sobre el conjunto que llama al método y para cada elemento se verifica que no esté en el
conjunto parámetro, si es el caso, lo elimina del conjunto que llama al método.
/**
* Método que devuelve la intersección de dos conjuntos
* @param Conjunto -- conjunto que intersecta con el conjunto que
14 CAPÍTULO 1. TIPOS ABSTRACTOS DE DATOS
Iterator it = iterador();
while (it.hasNext()) {
Object elemento = it.next();
if (!c.contiene(elemento))
cInterseccion.eliminar(elemento);
}
return cInterseccion;
}
Método 1.14. El método que calcula la diferencia de dos conjuntos es similar en su imple-
mentación al método anterior, excepto que en este caso se eliminan los elementos que están
en ambos conjuntos.
/**
* Método que devuelve la diferencia de dos conjuntos
* @param Conjunto -- conjunto con el que se hará la diferencia
* @return Conjunto -- conjunto con la diferencia
*/
public Conjunto diferencia(Conjuntable c) {
Conjunto cMenos = new Conjunto(this);
Iterator it = iterador();
while (it.hasNext()) {
Object elemento = it.next();
if (c.contiene(elemento))
cMenos.eliminar(elemento);
}
return cMenos;
}
/**
* Método para determinar si un conjunto es subconjunto de otro
1.6. ANÁLISIS DE ALGORITMOS 15
if (a > 0) {
suma += a;
datos++;
} else {
a*= (-1);
}
Éste tomarı́a una unidad de tiempo para la condición más dos para las asignaciones de
la instrucción if (tiene más que el else), es decir, tardarı́a tres unidades de tiempo,
por lo tanto es de orden O(1).
4. Ciclos. La complejidad de un ciclo se calcula utilizando la regla de la multiplicación.
Para ello se toma el tiempo de ejecución de su cuerpo multiplicado por el número de
veces que se realiza. El caso más sencillo es cuando están fijos el valor inicial y el de la
condicional y el cuerpo toma un tiempo constante. Ejemplo:
Este ciclo se realiza n veces y el cuerpo toma un tiempo constante cada vez, por tanto,
el tiempo de ejecución de este ciclo es O(1 ∗ n) = O(n).
Un análisis un poco más complejo es el requerido para el ciclo presentado en siguiente
método:
Este algoritmo tiene complejidad n2 , porque para cada uno de los n valores de i se
realiza la instrucción for interna, que es de complejidad n debido a que realiza n veces
su cuerpo, que tarda un tiempo constante en ejecutarse.
El siguiente ejemplo también es fácil de analizar:
El ciclo más interno tiene complejidad n debido a que se realiza n veces y su cuerpo es
de complejidad 1, el ciclo de en medio es de complejidad n2 porque se realiza n veces
pero, como se explicó, el ciclo que es su cuerpo tiene complejidad n. Finalmente, el ciclo
externo se realiza n veces y la complejidad de su cuerpo es n2 , lo que al multiplicarse
da n3 como complejidad del ciclo externo.
Cuando los lı́mites de las iteraciones están relacionados con los ı́ndices externos, el
análisis se vuelve más complejo.
√
El método esPrimo tiene una complejidad n, como se explicó anteriormente. Este
valor se multiplica por n que es el número de veces en que√se realiza la instrucción for,
por tanto el método imprimirPrimo tiene complejidad n n
• Logarı́tmico. O(log2 (n)) algoritmos que sucesivamente descartan una cantidad de da-
tos, generalmente la mitad, para ser procesados son los que tı́picamente caen en es-
ta categorı́a. Estos algoritmos se consideran eficientes. Ejemplo, la búsqueda binaria
(véase apéndice A).
• Casi lineal, llamados de orden n logaritmo de n. O(nlog(n)), algoritmos con esta com-
plejidad aparecen en ciclos donde el cuerpo es de orden logarı́tmico. Se consideran
algoritmos eficientes.
• Lineal. O(n) algoritmos con esta complejidad son aquellos que trabajan con todos los
datos. Ejemplo, búsqueda de un elemento en un conjunto desordenado.
Ejemplo 1.4. Análisis del método tamanio de la clase Conjunto visto en la sección 1.4.
cuyo cuerpo se reproduce a continuación:
El peor caso para calcular el tamaño de un conjunto con el método anterior se presenta cuando
el conjunto está lleno, debido a que es necesario recorrer todo el arreglo. Cada instrucción de
asignación se realiza en un tiempo constante c, y si el arreglo tiene n localidades, cuando el
conjunto está lleno es necesario hacer n veces la instrucción if. Si cada una se realiza en un
tiempo constante c, entonces el método toma c + (c × n) + c unidades de tiempo en realizarse.
Expresado de manera formal se dice que el algoritmo tiene complejidad O(c ∗ (n + 2)). En
el análisis de algoritmos se busca una cota superior, por eso no se toman en cuenta las
constantes, es decir, no se dice O(c ∗ (n + 2) la forma correcta es O(n). Si cada comparación
toma 1 segundo y se tiene un arreglo de 1000 datos, el método tardará 1002 segundos en
terminar. Si n = 2000 entonces el tiempo es 2002, casi el doble de 1000. Si n = 500 entonces
el tiempo es 502, casi la mitad de 1000. Si se tienen 3000 datos, el tiempo que toma es 3002,
prácticamente el triple. Se puede observar que el tiempo de ejecución del método depende
de la cantidad de los datos de entrada y las constantes son irrelevantes. Se puede hacer
la demostración formal de este resultado, pero para los fines con que se usa el análisis de
algoritmos en este texto basta con la explicación anterior.
Como puede observarse la mayorı́a de los métodos son O(n). Se puede tener una imple-
mentación más eficiente de este TAD con sólo utilizar una variable que indique cuál es la
1.7. MEJORA AL TAD CONJUNTO 21
/**
* Clase para el tipo abstracto de datos Conjunto.
* @author Amparo López Gaona
* @version 2.
*/
public class Conjunto implements Conjuntable {
private Object[] datos; // Almacenamiento para el conjunto
private int nDatos; // Cantidad de datos almacenados
/**
* Constructor de un conjunto con capacidad para 20 elementos.
*/
public Conjunto() {
this(20);
}
/**
* Constructor de un conjunto con capacidad para los elementos indicados.
* @param tam capacidad del conjunto.
*/
public Conjunto(int tam) {
datos = new Object[(tam <= 0) ? 20: tam];
nDatos = 0;
}
/**
* Constructor de copia.
* @param Conjunto -- conjunto que se tomará como valor inicial para
* crear el nuevo.
*/
public Conjunto(Conjunto c) {
datos = new Object[c.datos.length];
Como puede observarse, los constructores son prácticamente iguales en esta versión y en
la anterior con la excepción de que ahora se actualiza la variable nDatos que lleve registro
de la cantidad de datos en el conjunto.
Método 1.16. El método para determinar si un conjunto está vacı́o simplemente verifica
que el valor de la variable nDatos sea igual a cero, en caso contrario el conjunto no está vacı́o.
/**
* Determina si el conjunto tiene elementos o no.
* @return boolean - Devuelve true si el conjunto no tiene elementos y
* false en otro caso.
*/
public boolean estaVacio(){
return (nDatos == 0);
}
Método 1.17. El método para dejar conjunto vacı́o simplemente asigna a la variable nDatos
el valor cero.
/**
* Vacı́a el contenido de un conjunto.
* @return boolean - Devuelve true si el conjunto no tiene elementos y
* false en otro caso.
*/
public void vaciar(){
nDatos = 0;
}
Método 1.18. El método para dejar vacı́o un conjunto simplemente asigna a la variable
nDatos el valor cero.
/**
* Vacı́a el contenido de un conjunto
*/
public void vaciar(){
nDatos = 0;
}
Método 1.19. El método tamanio devuelve el valor de la variable nDatos, que es la cantidad
de elementos del conjunto.
/**
* Devuelve la cantidad de elementos que tiene el conjunto.
* @return int - cantidad de elementos que tiene el conjunto.
1.7. MEJORA AL TAD CONJUNTO 23
*/
public int tamanio(){
return nDatos;
}
/**
* Determina si un elemento está contenido en el conjunto.
* @param elemento - elemento que se desea saber si está en el conjunto.
* @return boolean - devuelve true si el elemento está en el conjunto y
* false en otro caso.
*/
public boolean contiene (Object elemento){
if (!estaVacio())
for (int i = 0; i < nDatos; i++)
if (elemento.equals(datos[i])) {
return true;
}
return false;
}
Método 1.21. El método eliminar quita un elemento del conjunto sustituyéndolo por el
que está al final del mismo.
/**
* Elimina el elemento especificado del conjunto.
* @param elemento - elemento que se desea eliminar del conjunto.
*/
public void eliminar(Object elemento){
for (int i = 0; i < nDatos; i++)
if (elemento.equals(datos[i])){
datos[j] = datos[nDatos--];
return;
}
}
Método 1.22. El método agregar inserta un nuevo elemento en el conjunto, para ello debe
verificar primero que no exista este elemento.
/**
24 CAPÍTULO 1. TIPOS ABSTRACTOS DE DATOS
Es importante notar que cambia la implementación del iterador, pero la forma de uso
permanece intacta. El usuario no se entera que cambió la implementación ni de la clase, ni
del iterador porque se siguen implementando las mismas interfaces.
La implementación de los métodos que utilizan el iterador no cambia, pues como se men-
ciona en el párrafo anterior, éste se sigue utilizando igual en tanto la interfaz no cambia, sólo
la implementación. El resultado de hacer los cálculos correspondientes de la complejidad de
los métodos de la segunda versión del TAD Conjunto es el presentado en la tabla 1.2.:
Los métodos contiene, eliminar y agregar siguen teniendo la misma complejidad por-
que en el peor caso es necesario recorrer todo el arreglo, sin embargo, en esta versión los
otros métodos tienen orden constante, lo cual es inmejorable. Cabe resaltar que el cambio
fue mı́nimo, agregar una variable que sirve de contador, sin embargo, el beneficio fue muy
grande al reducir la complejidad de la mayorı́a de los métodos.
Otra mejora que puede hacerse a la clase Conjunto en cuanto a funcionalidad aunque no
en cuanto a velocidad consiste en modificar el método agregar para que cuando se requiera
agregar un elemento al conjunto y éste se encuentre lleno, el arreglo “crezca” y no lance una
excepción.
Es sabido que arreglo es la única estructura de datos que proporciona Java y que su gran
ventaja es que acceder a cualquier elemento de él toma siempre el mismo tiempo, sin embargo
una vez definido su tamaño éste no puede cambiar, por lo tanto los arreglos no pueden crecer.
En esta sección se presenta una forma de hacerlo.
Método 1.23. Método para agregar un elemento a un conjunto sin preocuparse por el
tamaño de éste. Si el arreglo está lleno, se llama al método privado crecerArreglo.
/**
* Agrega un elemento al conjunto, siempre y cuando no exista.
26 CAPÍTULO 1. TIPOS ABSTRACTOS DE DATOS
Método 1.24. Método privado para aumentar la capacidad de un conjunto, para ello crea
un arreglo más grande que el original, luego copia todos los datos del arreglo original al
nuevo y finalmente copia la referencia del nuevo arreglo en el original, con lo cual a partir
de ese momento el original tiene un tamaño mayor.
/*
* Aumenta la capacidad del arreglo.
* @param - nueva capacidad para el arreglo
*/
private void crecerArreglo() {
int tamanoNuevo = datos.length +10;
Object [] arregloNuevo = new Object[tamanoNuevo];
//Copia los elementos del arreglo anterior
for (int i = 0; i < nDatos; i++) {
arregloNuevo[i] = datos[i];
}
datos = arregloNuevo;
}
1.8. Ejercicios
1. Implementar un método para la clase Conjunto que calcule el conjunto potencia del
conjunto dado. El conjunto potencia es el conjunto de todos sus subconjuntos. Especi-
ficar la complejidad del método.
3. Desarrollar un programa que lea un texto y muestre como salida las palabras que
aparecen en él, indicando cuántas veces aparece cada una.
4. Implementar un tipo abstracto de datos para trabajar con una colección de datos en
la cual los elementos se almacenan sin importar si se repiten y no tienen un orden
definido. La interfaz que se debe implementar es la siguiente:
5. Escribir una tabla con la complejidad de los métodos del TAD para colecciones de
datos desordenados y repetidos que implementa la interfaz Coleccionable.
1.8. EJERCICIOS 29
6. Implementar un tipo abstracto de datos para trabajar con una colección de datos
ordenados. La interfaz que se debe implementar es la siguiente:
7. Escribir una tabla con la complejidad de los métodos del TAD para colecciones de
datos ordenados y repetidos que implementa la interfaz Ordenable.
8. Implementar un TAD para trabajar con arreglos bidimensionales, conocidos como ma-
trices. La interfaz para este tipo de datos es la siguiente:
interface Dimensionable {
public boolean estaVacio ();
public int renglones();
public int columnas();
public void insertar(Object valor, int renglon, int columna);
public Object obtener(int renglon, int columna);
public void eliminar(int renglon, int columna);
public void reemplazar(Object valor, int renglon, int columna);
public Dimensionable transponer ();
public boolean esSimetrica();
public java.util.Iterator iterador();
}
9. Escribir una tabla con la complejidad de los métodos del TAD Matriz que implementa
la interfaz Dimensionable.
10. Implementar un tipo abstracto de datos para trabajar con mapas ordenados (también
llamados tablas, diccionarios o tablas de búsqueda). En un mapa los elementos se
almacenan en parejas, cada una consta de una llave y un valor. Para recuperar un
valor es necesario proporcionar la llave y se obtiene el valor asociado a ella. Cada llave
identifica una entrada, por lo tanto debe ser única. Sin embargo, es posible que dos
llaves diferentes tengan asociado el mismo valor. La interfaz que se debe implementar
es la siguiente:
11. Escribir una tabla con la complejidad de los métodos del TAD para trabajar con mapas
ordenados que implementa la interfaz Mapeable.
Capı́tulo 2
Listas
Las estructuras de datos son una forma de almacenar información en la computadora para
que pueda ser utilizada en manera eficiente, donde por eficiencia se entiende la habilidad de
encontrar y manipular los datos con rapidez y con el mı́nimo de recursos, como tiempo de
proceso y espacio en memoria. En las estructuras de datos, las menos restrictivas son las listas,
porque no imponen restricciones al contenido ni a la forma de acceder a sus elementos. En
este capı́tulo se presenta la definición del TAD Lista, varias implementaciones y aplicaciones
del mismo.
2.1. Introducción
Las listas aparecen frecuentemente en la vida real, a manera de ejemplo se tienen; lista de
compras, lista de útiles escolares, lista de invitados, lista de pendientes, lista de tareas, lista
de discos, etc. Se puede definir una lista como una estructura de datos en la cual es irrelevante
el orden y manejo de los elementos que contiene, es decir las inserciones y supresiones pueden
ser en cualquier lugar.
Ejemplo 2.1. Como ejemplo de uso de listas en computación se tiene el siguiente: suponer
que se requiere escribir una lista con los identificadores contenidos en un programa escrito en
Java. Cada identificador en esta lista debe estar acompañado de una lista con el número de
cada una de las lı́neas en las que aparece. Por ejemplo, al proporcionar el siguiente archivo
como entrada al programa mencionado:
import java.util.Iterator;
class PruebaLista {
public static void main(String [] pps) {
Lista lis = new Lista();
33
34 CAPÍTULO 2. LISTAS
lis.agregar(new Integer(i));
Iterator i = lis.iterador();
while(i.hasNext()) {
Integer entero = (Integer) i.next();
if ((entero.intValue()) %2 == 0)
lis.eliminar(entero);
}
i = lis.iterador();
while(i.hasNext())
System.out.println(i.next());
}
}
java: 1,
util: 1,
Iterator: 10, 1,
PruebaLista: 3,
String: 4,
pps: 4,
Lista: 5, 5,
lis: 16, 14, 10, 8, 5,
i: 18, 17, 16, 12, 11, 10, 8, 7, 7, 7,
agregar: 8,
Integer: 12, 12, 8,
elementos: 16, 10,
hasNext: 17, 11,
entero: 14, 13, 12,
next: 18, 12,
intValue: 13,
eliminar: 14,
System: 18,
out: 18,
println: 18,
• contiene. Regresa true si el elemento está en la lista y false en otro caso. Este
método no cambia el estado de la lista.
• vaciar. Elimina todos los elementos de la lista. El tamaño de la lista después de esta
operación es cero.
/**
* Clase para almacenar una pareja constituida por un nombre y una lista.
* @author Amparo López Gaona
* @version Abril 2011
*/
class IdyLista {
private String nombre;
private Lista lista;
/**
* Método para obtener la lista del objeto
* @Lista -- lista del objeto
*/
public Lista obtenerLista() {
return lista;
}
}
Clase 2.1. Clase para crear la lista de identificadores con su respectiva lista con números
de lı́nea.
import java.util.Iterator;
/**
* Clase para trabajar una lista donde cada elemento contiene a su vez una lista.
* @author Amparo López Gaona
* @version Abril 2011
*/
class ListaDeIds {
Lista ids;
/**
* Constructor por omisión
*/
ListaDeIds() {
ids = new Lista();
}
/**
* Método que permite insertar en una lista, cuyo nombre es dado, el
* elemento especificado
* @param identificador - nombre de la lista en que se hará la inserción
* @param linea - elemento que se insertará
*/
public void insertar(String identificador, Integer linea) {
Método 2.2. Método para imprimir la lista. En este método se utilizan dos iteradores
anidados, el primero para moverse a lo largo de la lista de identificadores; para cada uno se
utiliza otro iterador para moverse en la lista de números de lı́nea.
/**
* Método para imprimir la lista
*/
public void imprimir() {
for(Iterator it = ids.iterador(); it.hasNext(); ) {
IdyLista idLista = (IdyLista) it.next();
System.out.print(idLista.obtenerNombre() + ": ");
Lista lista = idLista.obtenerLista();
for (Iterator ilista = lista.iterador(); ilista.hasNext(); ) {
System.out.print(ilista.next()+ ", ");
}
System.out.println();
}
}
Clase 2.2. Clase para generar la lista de identificadores con su número de lı́nea. Su trabajo
consiste en crear una lista con las palabras reservas tomada del primer parámetro del método
main, abrir el archivo con el programa fuente (segundo parámetro del método main), leerlo
y mientras haya palabras en él verificar que no sea una reservada, si es el caso insertarla en
la lista y por último imprimir tal lista.
/**
* Clase para generar un lista de palabras no reservadas cada una con una lista
* con los números de lı́nea en que aparece.
2.3. APLICACIONES DE LISTAS 39
if (pps.length != 2) {
System.out.println("Forma de uso: ListaPalabrasReservadas archivoFuente");
System.exit(0);
}
leerReservadas(pps[0]);
try {
BufferedReader in = new BufferedReader (new FileReader(pps[0]));
StreamTokenizer tok = new StreamTokenizer(in);
tok.ordinaryChar(’.’);
tipoTok = tok.nextToken();
lisId.imprimir();
} catch(IOException e) {
System.out.println("Se genero IOException "+e);
}
}
}
Dicho examen cuenta con 100 preguntas. Conforme los alumnos terminan el examen se cali-
fica y se registra en una lista el nombre del alumno, su identificación y el número de aciertos
obtenidos. Obviamente esta lista no tiene un orden que facilite las búsquedas en ella. Pue-
de haber muchos usos para esta lista, en particular, se requiere determinar cuáles alumnos
tuvieron la mejor calificación.
Una solución al problema es ordenar la lista de alumnos por el número de aciertos obteni-
dos. Para la implementación de la solución se puede usar cualquier algoritmo de ordenamien-
to. Sin embargo, en esta sección se presenta un algoritmo muy particular para cuando los
elementos a ordenar están en un rango de valores numéricos pequeño; este algoritmo utiliza
listas. El algoritmo utilizado es el llamado ordenamiento en recipientes (bin-sort).
Si se sabe que el atributo por el cual se va a ordenar una serie de datos tiene un rango de
valores pequeño entonces se puede ordenar con el algoritmo siguiente:
• Crear un arreglo de recipientes (bins), uno para cada valor del atributo por el cual se
va a ordenar. Lo recomendable es que cada recipiente se implemente como una lista.
Este algoritmo es bastante eficiente sólo que está restringido a datos con las caracterı́sticas
mencionadas anteriormente. Si la lista original tiene n elementos y hay m recipientes, el
algoritmo es de orden O(n + m), si m <= n se tiene O(n), pero si m > n entonces es de
O(m) por lo cual la complejidad del algoritmo es lineal.
A diferencia de otros algoritmos de ordenamiento, éste requiere memoria adicional para
cada recipiente y por lo tanto es buen ejemplo de equilibrio entre espacio y rendimiento.
Ejemplo 2.3. A continuación se presenta una implementación del algoritmo de ordenamiento
en recipientes. Se asume que se tiene una clase Alumno con los métodos necesarios para
manipular sus atributos y en particular hay uno obtenerAciertos que, como su nombre
indica, permite conocer la cantidad de aciertos que obtuvo el alumno en el examen.
/**
* Método para ordenar datos en un rango especı́fico usando recipientes (binsort)
* @param datos -- lista con los datos a ordenar
* @param rango -- lı́mite superior del rango de valores a tomar en cuenta.
*/
2.3. APLICACIONES DE LISTAS 41
El problema consiste en determinar el orden en que los hombres son eliminados y quién se
salva; para hacerlo se recibe un número n, la cantidad de soldados y el lugar que ocupa el
soldado a partir de donde se empezará la cuenta.
Este problema es una adaptación a una leyenda sobre el historiador Flavius Josephus en
el primer siglo de nuestra era. En la literatura existen varias versiones de este problema
además existe un algoritmo para determinar tanto el número n, como la posición inicial para
asegurar que un hombre particular se salve.
Ejemplo 2.4. Clase que contiene un método para resolver el problema de José. El método
recibe una lista con el nombre de cada soldado, el tamaño de la lista y el número n para ir
eliminando a los soldados. En esta versión la posición inicial es siempre la primera y muestra
el orden en que se van descartando los soldados.
/**
* Método para resolver el problema de José
* @param listaPersonas -- Lista con los datos de las personas
* @param nPersonas -- entero con la cantidad de personas en la lista
* @param numero -- entero para saber cada cuántos se elimina una persona
*/
public void jose(Lista listaPersonas, int nPersonas, int numero) {
Iterator itr = listaPersonas.iterador();
Object soldadoFuera = null;
Ejemplo 2.5. Clase para probar la solución al problema de José. Este programa recibe dos
parámetros: el primero es la cantidad de soldados y el segundo cada cuántos soldados se
elimina alguno.
try {
if(pps.length != 2) {
System.err.println("Usar: Jose NPersonas numero");
} else {
p1 = Integer.parseInt(pps[0]);
p2 = Integer.parseInt(pps[1]);
En este programa se valida que haya dos parámetros y que sean enteros, si es es el caso se
crea un objeto de la clase Jose, se generan cadenas simulando los nombres de los soldados,
se llama a ejecutar el método jose y se muestra el nombre del soldado elegido para ir a pedir
ayuda.
La forma más sencilla de implementar una lista es mediante un arreglo, sin embargo, es
sabido que con un arreglo se debe conocer de antemano la cantidad máxima de datos que se
pueden almacenar en él. Para salvar esta restricción se puede usar una lista ligada (figura
2.1.). Una lista ligada es una agrupación de objetos denominados nodos, no necesariamente
almacenados en forma adyacente. Cada nodo contiene el elemento (o dato) y un enlace o liga
a su sucesor. El último elemento tendrá un enlace con valor null para indicar que no tiene
sucesor.
lista e1 e2 e3 e4 e5
Se dice que una lista ligada es una estructura dinámica, pues no se determina su capacidad
máxima al momento de su creación. Cada vez que se inserta un elemento en una lista ligada,
crece y si se eliminan elementos decrece.
Una lista ligada suele tener un principio y un fin, pero no se puede llegar en tiempo
constante a cualquier elemento por su posición. El acceso a los elementos en la lista es
secuencial, es decir, para acceder a cualquier elemento es necesario recorrer secuencialmente
los elementos en la lista hasta llegar al elemento deseado.
Las listas ligadas, como se han descrito, pueden variar al implementarse, si se decide tener
un apuntador al inicio de la lista, un apuntador al final de la lista, si la lista terminará con
el valor null, como se mostró en la figura, o bien con un nodo especial, si se usará una sola
liga o bien dos. En esta sección se presentan sólo un par de implementaciones; cada una de
ellas se puede usar para resolver los problemas presentados en la sección 2.3.
Clase 2.3. Implementación de la clase para los nodos de una lista ligada. La estructura de
cada nodo consta de un objeto de la clase Object, que es el dato que almacena, esto con
el propósito de hacerla genérica. El otro atributo de los nodos es una referencia al siguiente
nodo.
/**
* Clase para manejar los nodos de la lista.
* @author Amparo López Gaona
* @version abril 2011
*/
public class Nodo {
public Object elemento;
public Nodo sgte;
/**
2.4. IMPLEMENTACIÓN DE LISTAS 45
En esta clase se tienen varias cosas curiosas. La primera es que los atributos no son privados.
En este caso se justifica tal decisión para facilitar la asignación de valor a los atributos por
la forma en que se trabajarán los mismos, como se verá más adelante en la programación de
algunos métodos.
La segunda es que se tiene una referencia a un objeto del tipo que se está definiendo, pero
es válido hacer esto. Al declarar un entero, por ejemplo int entero; se está especificando
que en la variable entero se tendrá cualquier valor entero válido. Si la declaración es Object
elemento; se está especificando que en elemento se tendrá la referencia a un objeto de la
clase Object, es decir, la dirección de un objeto. Al declarar Nodo sgte se especifica que en
este atributo se tiene la referencia a un objeto de la clase Nodo.
La tercera es que se asigna el objeto que se pasa como parámetro, no una copia de él, y
como se mencionó, esto puede traer problemas. No se puede evitar este problema porque la
clase Object no tiene implementado un constructor de copia ni el método clone, pero es
importante que el usuario del TAD pase como parámetro una copia del objeto con el que se
desea trabajar no el objeto mismo para evitar posibles sorpresas desagradables.
Clase 2.4. Implementación de la interfaz Listable presentada al inicio de este capı́tulo en
la cual se tiene una referencia al inicio de la lista y el valor null en el atributo sgte de un
nodo especifica el final de la lista.
Método 2.3. El constructor por omisión de la lista asigna el valor de null al nodo inicial,
denominado cabecera, es decir, se crea la lista vacı́a, la cual se representa gráficamente como
se muestra en la figura 2.2.
inicio
Método 2.4. El método estaVacia determina si una lista está vacı́a verificando que el nodo
inicial tenga como valor null.
/**
* Prueba que la lista esté vacı́a.
* @return true si está vacı́a y false en otro caso.
*/
public boolean estaVacia() {
return inicio == null;
}
Método 2.5. El método vaciar eliminar todos los elementos de la lista. Para ello basta
con asignar al nodo inicial el valor null con lo cual los nodos que formaban la lista quedan
inaccesibles y por lo tanto a disposición del recolector de basura.
/** Crea una lista vacı́a. */
public void vaciar() {
inicio = null;
}
Método 2.6. El método primerElemento permite obtener el primer elemento de una lista
no vacı́a. Para hacerlo toma el valor del atributo elemento del nodo inicial.
/**
* Devuelve el primer elemento de la lista si no está vacı́a
* @throws NoSuchElementException -- en caso de no existir el elemento
* en la lista
**/
2.4. IMPLEMENTACIÓN DE LISTAS 47
Método 2.7. El método contiene se utiliza para determinar si un objeto está en la lista o
no. Para su implementación se hace uso del método interno buscar que recorre la lista hasta
encontrar el dato y devuelve el nodo en que se encuentra, si no lo encuentra devuelve null.1
/**
* Determina si un elemento está contenido en la lista.
* @param dato el elemento a buscar.
* @return boolean - true si el dato está en la lista y false en otro caso.
*/
public boolean contiene(Object dato) {
return buscar(dato) != null;
}
/*
* Devuelve la posición del nodo que contiene el dato buscado.
* @param dato el dato a buscar.
* @return un nodo; null si el dato no se encuentra.
*/
private Nodo buscar(Object dato) {
Nodo pos = inicio;
Método 2.8. El método sustituir cambia el valor de un nodo. Este método busca el
primer nodo con el valor original, y si lo encuentra sustituye ese valor por el nuevo. En caso
de no encontrar el elemento dispara la excepción NoSuchElementException.
Método 2.9. El método agregar inserta un elemento al inicio de la lista, haciendo uso del
constructor de la clase Nodo.2 Independientemente de si la lista está vacı́a o no basta con
actualizar el valor de inicio para que contenga la referencia al nuevo nodo, y este nuevo nodo
tendrá como elemento siguiente el que hasta antes de su llegada era el nodo inicial (figura
2.3.).
inicio inicio e1
inicio e2 e3 inicio e2 e3
/**
* Inserta el primer elemento de la lista.
* @param dato el dato a agregar.
*/
public void agregar(Object dato) {
inicio = new Nodo(dato,inicio);
}
Método 2.10. El método para eliminar un elemento de la lista busca el elemento a eliminar
y conserva la referencia al nodo anterior, pues ésta se debe modificar para que apunte al
nodo sucesor del nodo que se va a eliminar, con lo cual el nodo a eliminar queda inaccesible
y por lo tanto eliminado (figura 2.4.).
2
Como es irrelevante el lugar en donde se agreguen los elementos a la lista, por facilidad se decidió hacerlo
al inicio de la lista.
2.4. IMPLEMENTACIÓN DE LISTAS 49
Antes de borrar e2
inicio e1 e2 e3 e4
Después de borrar e2
inicio e1 e2 e3 e4
/**
* Elimina la primera ocurrencia de un dato.
* @param dato -- el dato a eliminar.
*/
public void eliminar(Object dato) {
Nodo pos = inicio, anterior = null;
Para terminar la implementación del TAD Lista para la interfaz Listable se presenta la
implementación del iterador.
Método 2.11. Método iterador, con la clase interna que implementa su funcionamiento.
2.4.1. Complejidad
En esta sección se presenta una tabla con la complejidad de cada método de la implementa-
ción del TAD Lista que se presentó en la sección anterior.
/**
* Método para agregar un elemento al final de la lista.
* @param dato -- dato que se desea agregar
*/
public void agregarFinal(Object dato) {
if (estaVacı́a())
agregar(dato);
else {
for (Nodo p = inicio; p.sgte != null; p = p.sgte)
; //Encuentra el último nodo
p.sgte = new Nodo(dato); // Agrega el nuevo nodo
}
Para que este método también sea de orden constante es necesario incluir una nueva
referencia que esté siempre apuntando al final de la lista (véase figura 2.5.).
inicio fin
e1 e2 e3 e4 e5
Figura 2.5. Lista ligada con una referencia al inicio y otra al final.
Clase 2.5. Clase que implementa una lista ligada con dos referencias: una al inicio y otra
al final de la lista.
/**
* Lista ligada usando dos referencias: una al inicio y otra al final.
52 CAPÍTULO 2. LISTAS
Ahora cambia la implementación de aquellos métodos en los que se requiere que la refe-
rencia al final de la lista señale al nodo correspondiente. A continuación se muestran sólo los
métodos que cambian.
Método 2.13. Constructor por omisión. Inicializa tanto el nodo inicial como el final con
valor de null.
/** Construye la lista */
public Lista() {
inicio = fin = null;
}
Método 2.14. El método para probar si una lista está vacı́a. Ahora se debe verificar que
ambas referencias tengan valor null.
/** Prueba que la lista esté vacı́a.
* @return true si está vacı́a y false en otro caso.
*/
public boolean estaVacia() {
return inicio == null && fin == null;
}
Método 2.15. El método para eliminar todos los elementos de una lista asigna el valor null
a ambas referencias.
/** Crea una lista vacı́a. */
public void vaciar() {
inicio = fin =null;
}
/**
* Inserta el primer elemento de la lista.
* @param dato el dato a agregar.
*/
public void agregarAlInicio(Object dato) {
if (estaVacia())
inicio = fin = new Nodo(dato);
else
inicio = new Nodo(dato,inicio);
}
Método 2.18. El método agregar ahora lo hace al final de la lista, para ello es necesario
actualizar la referencia al último elemento de la misma.
/**
* Inserta el elemento al final de la lista.
* @param dato el dato a agregar.
*/
public void agregar(Object dato) {
if (estaVacia())
inicio = fin = new Nodo(dato);
else
fin = fin.sgte = new Nodo(dato);
}
Método 2.19. El método eliminar funciona igual que en la implementación anterior, excepto
que si se elimina el último elemento es necesario actualizar la referencia al final de la lista.
/**
* Elimina la primera ocurrencia de un dato.
* @param dato el dato a eliminar.
*/
public void eliminar(Object dato) {
Nodo pos = inicio, anterior = null;
En esta sección se presentó una segunda implementación para el TAD Lista, la cual incluye
más métodos de los definidos en la interfaz Listable. Esto es válido, pues la única restricción
al implementar una interfaz es implementar todos los métodos definidos en ella, pero pueden
agregarse otros, como se hizo en esta sección.
2.4.3. Complejidad
En la tabla 2.2. se muestra la complejidad de los métodos del TAD Lista, en el caso de
tener una referencia al inicio y otra al final de la lista.
Puede observarse que la introducción de la otra referencia permite que la complejidad
de los métodos agregarAlInicio, eliminarPrimero y ultimoElemento sea de orden 1,
además de que reduce la complejidad del método agregar, porque ahora es orden constante.
Otra posibilidad de implementación de las listas es utilizar en cada nodo dos referencias:
una en el siguiente nodo, como hasta ahora, y la otra en el nodo anterior. La funcionalidad
de las listas es casi la misma, excepto porque se pueden recorrer en cualquier dirección con
la misma facilidad. Se deja como ejercicio al lector.
2.5. EJERCICIOS 55
2.5. Ejercicios
1. Programar una clase ListaExtendida que sea subclase de la clase Lista presentada
en este capı́tulo y que, además de los métodos heredados, tenga los siguientes métodos:
2. Programar una clase ListaOrdenada que sea subclase de Lista, en ésta los elementos
almacenados deben estar ordenados, para ello los elemento de la lista deben imple-
mentar la interfaz Comparator y el constructor de la lista debe recibir un compara-
dor. En esta clase se debe incluir el método fundir(Lista lis) para obtener una
ListaOrdenada a partir de la intercalación de los elementos de la lista, que lo llama
con los de lis.
3. Crear una lista doblemente ligada que, como su nombre lo indica, está formada por
nodos que contienen una liga al siguiente elemento y una liga al elemento anterior de
la lista. Además de la información necesaria para el trabajo de la lista, incorporar un
cursor que permita recorrer la lista y programar las siguientes operaciones:
4. Escribir un programa que lea un archivo que tiene parejas (nombre-alumno, curso)
como sigue:
y genere dos tipos de listas: una con la lista de los alumnos inscritos en cada materia
y otra en la cual se liste para cada alumno los cursos en los que está inscrito. Como se
muestra a continuación:
(34) = 0100011
10
Utilizar una lista para almacenar el número binario. Este método puede escribirse
utilizando recursión.
• Obtener el número en cualquier base a partir de un número entero positivo en
base 10. Este método recibe el entero que debe convertir y la base a la que se
desea convertir.
• Obtener el número en base 10 de un número en cualquier base. Este método recibe
como parámetro una lista que contiene un número en cualquier base y la base en
la que está tal número.
6. Escribir un TAD para trabajar con polinomios de una variable de la forma Pn (x) =
A0 + A1 x + A2 x2 + A3 x3 + ... + An xn donde los coeficientes son reales.
Los métodos que debe incluir esta clase son:
(a) Un constructor por omisión para el polinomio 0x0
(b) Un constructor de copia.
(c) sumar(Polinomio p) para sumar dos polinomios.
(d) restar (Polinomio p) para restar dos polinomios.
(e) multiplicar(Polinomio p) para multiplicar dos polinomios.
(f) evaluar() para evaluar un polinomio.
(g) imprimir() para imprimir el polinomio.
(h) grado() para obtener el grado del polinomio.
(i) grado(int n) para obtener el grado del n-ésimo término.
(j) coeficiente(int n) para obtener el coeficiente del n-ésimo término.
Capı́tulo 3
Pilas
Una pila es una estructura de datos cuya única restricción está en la forma de acceder a los
elementos almacenados en ella, ya que tanto la entrada como la salida de los datos es por un
solo lugar. Aunque parece ser una restricción muy fuerte, esta estructura es muy sencilla de
implementar y sumamente útil. En este capı́tulo se presenta el TAD Pila, algunas de sus apli-
caciones y una implementación con el análisis de la complejidad de los métodos que lo forman.
3.1. Introducción
En ocasiones es necesario restringir la forma de acceso a los datos almacenados en una
estructura, por ejemplo, puede resultar útil que los datos se recuperen en el orden inverso a
como se almacenaron. Ejemplo de esto se tiene al navegar en páginas web con las flechas que
permiten moverse hacia adelante y hacia atrás, siempre se regresa a la anterior y si se quiere
desandar el camino esto se hace exactamente a la inversa de como se recorrió el camino. Para
problemas como este existe el TAD Pila.
Salida Entrada
D3 Tope
D2
D1
Una pila es una estructura de datos con un solo lugar de acceso a ellos (figura 3.1.), debido
a esto el último elemento en almacenarse es el primero en utilizarse, de ahı́ que las pilas
también se conozcan como LIFO (last in, first out).
59
60 CAPÍTULO 3. PILAS
interfaz Apilable {
public boolean estaVacia();
public void vaciar();
public void push(Object);
public Object pop();
public Object top();
public int tamanio();
public java.util.Iterator iterador();
}
• vaciar. Elimina todos los elementos de la pila, es decir, deja vacı́a la pila. El tamaño
de la pila después de esta operación debe ser cero.
• top. Regresa el valor del último elemento que se insertó en la pila o bien null si ésta
se encuentra vacı́a. Con este método no se altera el estado de la pila.
Puede apreciarse que son pocas las operaciones con pilas, sin embargo son muy útiles,
como se verá en la siguiente sección.
3.3. APLICACIONES DE PILAS 61
Para facilitar la expresión de la solución al problema los discos se identifican con un número
entero de 1 a n que corresponde al diámetro del disco y los postes se identifican con las letras
A, B y C. Si la cantidad de discos es 3, la solución al problema consta de los siguientes pasos:
Mover el disco 1 del palo A al B
Mover el disco 2 del palo A al C
Mover el disco 1 del palo B al C
Mover el disco 3 del palo A al B
Mover el disco 1 del palo C al A
Mover el disco 2 del palo C al B
Mover el disco 1 del palo A al B
Se puede observar que para 3 discos se requieren 7 movimientos. En general para n discos
se requieren 2n −1 movimientos. Existe una leyenda que dice que en la ciudad de Hanoi viven
unos monjes dedicados a resolver el problema con 64 discos. De ahı́ que este problema se
conoce como el problema de las torres de Hanoi. Si mover cada disco toma un dı́a, entonces
resolver el problema tomará 264 − 1 dı́as, sin hacer ningún movimiento erróneo, que supone
una cantidad considerable de años. La leyenda dice que cuando resuelvan el problema el
mundo terminará.
62 CAPÍTULO 3. PILAS
Ejemplo 3.1. Programa que resuelve el problema de las torres de Hanoi. Para la solución
programada de este problema cada palo se representa como una pila, puesto que sólo hay un
punto de acceso, y cada disco por un número entero que simboliza el diámetro del disco.
/**
* Clase para resolver el problema de las torres de Hanoi
* @author Amparo López Gaona
*/
public class Hanoi {
private Pila[] palo; // Arreglo de palos
private final int nDiscos; // Cantidad de discos
/**
* Constructor por omisión, crea 3 discos.
*/
public Hanoi () {
this (3);
/**
* Constructor que crea la candidad de discos especificada
* @param int -- cantidad de discos a crear
*/
public Hanoi(int n) {
System.out.println("Torres de Hanoi");
nDiscos = n;
/**
* Metodo para mostrar el contenido de cada palo
*/
public void pinta () {
java.util.Iterator it1 = palo[1].iterador();
3.3. APLICACIONES DE PILAS 63
La solución al problema consiste en pasar primero el disco1 del palo1 al palo2. Una
vez hecho esto, el problema se reduce a pasar los n − 1 discos restantes del palo1 al palo3
y finalmente regresar esos n − 1 discos del palo3 al palo2. La complejidad del algoritmo
está determinada por la cantidad de movimientos requeridos, de ahı́ que este algoritmo sea
de O(2n ).
64 CAPÍTULO 3. PILAS
Ejemplo 3.2. La salida del programa para 3 discos se muestra a continuación; puede verse
el comportamiento como pila de cada palo.
Torres de Hanoi
Las torres inicialmente tienen
Palo1 Palo2 Palo3
*
**
***
Palo1 Palo2 Palo3
** *
***
forma de determinar, usando una pila, si una expresión que contiene paréntesis los tiene
balanceados. El segundo ejemplo consiste en evaluar una expresión aritmética.
Balanceo de elementos
Un problema común en los traductores es determinar si una expresión aritmética tiene bien
anidados sus paréntesis. Para ello se debe verificar que haya tantos paréntesis de apertura, o
del lado izquierdo, como paréntesis de cerrado, o lado derecho. Además, en ningún momento
puede haber más paréntesis derechos que izquierdos. Descrito ası́ puede parecer complicado
de resolver, pero la solución se simplifica si se utiliza una pila en la que se van metiendo
los paréntesis izquierdos y cada vez que se encuentra uno derecho se saca de la pila. Si se
termina de recorrer la expresión y la pila está vacı́a, entonces la expresión tiene sus paréntesis
balanceados. En cualquier otro caso ocurre un error.
Esta solución puede generalizarse al considerarse tres tipos de paréntesis: los tradicionales,
los cuadrados o corchetes y las llaves. En este caso se requiere que no se tengan más paréntesis
de un tipo que de otro y que cierren adecuadamente. Por ejemplo,
(a+[b*c]/[d-h])*25 es correcta
{a+{b+c+{d+e}+e}} es correcta
{a+{b+c+{d+e}+e} es incorrecta
((a+b} es incorrecta
(a) Si es un paréntesis que abre "(", "[" o bien "{", meterlo a la pila.
(b) Si es un paréntesis que cierra y la pila está vacı́a, reportar que la expresión no
tiene balanceados sus paréntesis, pues hay más del lado derecho que izquierdo.
(c) Si es un paréntesis que cierra y la pila no está vacı́a, sacar de la pila el carácter y
verificar que corresponda con el sı́mbolo que abre. Si no es ası́ reportar un error.
(d) Ignorar cualquier otro elemento.
Ejemplo 3.3. Programa para determinar si una expresión tiene balanceados sus paréntesis.
/** Programa para verificar que una expresión tiene balanceados sus paréntesis
* @author Amparo López Gaona
*/
66 CAPÍTULO 3. PILAS
if (pila.estaVacia())
System.out.println("Parentesis balanceados");
else
System.out.println("Parentesis NO balanceados");
}
/* Método privado que verifica los paréntesis
* Recibe un paréntesis de cerrado y verifica que en el tope de la
* pila esté el equivante de apertura.
*/
private void verifica (char c) {
if (pila.estaVacia()) {
System.out.println("Parentesis NO balanceados");
} else {
Character s = pila.pop();
if (c != s.charValue())
System.out.println("Parentesis NO balanceados");
}
}
}
3.3. APLICACIONES DE PILAS 67
El ejemplo se mostró con expresiones aritméticas, pero podrı́a ser más amplia la “expresión”
que se desee validar. Por ejemplo, las llaves en un programa en Java. También con esta
misma idea se pueden solucionar otros problemas parecidos, por ejemplo, verificar que si en
un programa se tienen instrucciones if anidadas éstas estén anidadas correctamente, o en
documentos escritos en XML verificar que las etiquetas estén bien anidadas.
Infija Postfija
A+B*C ABC*+
(A+B)*C AB+C*
A+B-C AB+C-
(A+B)*(C-D) AB+CD-*
((A+B)*C-(D-E))ˆ (F+G) AB+C*DE–FG+ˆ
Una expresión en notación infija puede prestarse a ambigüedades, por ejemplo, la expresión
a+b*c puede interpretarse como (a+b)*c o bien como a+(b*c), para resolver este problema
se asigna prioridad a los operadores y/o se incluyen paréntesis como se acaba de ver. Las
expresiones en notación prefija y postfija no presentan la ambigüedad explicada antes, por
lo tanto las expresiones en esta notación no requieren de paréntesis.
Una vez que se tiene una expresión aritmética en notación postfija su evaluación es muy
sencilla, y también requiere de una pila. El algoritmo es el siguiente:
3. Leer el signo de suma. Por ser un operador, se sacan los dos elementos del tope de la
pila y se realiza la suma 3+4.
6. Leer el signo de multiplicación, entonces se sacan los dos elementos del tope de la pila
y se realiza la operación 7*9.
8. Como ya no hay más elementos en la expresión se saca el valor que está en la pila y
que es el resultado de la evaluación. Es decir, el resultado de evaluar la expresión es
63.
4. Leer el signo de multiplicación entonces se sacan los dos elementos del tope de la pila
y se realiza la multiplicación 4*9.
3 4 4 3 7
4
3 3 3 7
9 9 7 63
9
7 7 63
op1 = 3 op1 = 3 op1 = 7 op1 = 7
op2 = 4 op2 = 9 op2 = 9 op2 = 9
6. Leer el signo de suma entonces se sacan los dos elementos del tope de la pila y se realiza
la suma 36 + 3.
8. Como se ya no hay más elementos en la expresión se saca el valor que está en la pila y
que es el resultado de la evaluación. Es decir el resultado de evaluar la expresión es 39.
Método 3.1. Método que implementa el algoritmo para la evaluación de expresiones aritméti-
cas en notación postfija.
/**
* Método que recibe una expresión en notación postfija y la evalúa.
* @param String -- cadena con la expresión en posfija
* @return double -- valor de la expresión
*/
public double calcular (String expresion) {
Pila pila = new Pila();
StringTokenizer tokenizer;
String token;
70 CAPÍTULO 3. PILAS
3 4 9 9 4
9
4 4 4
3 3 3 3 3
36 36 3 39
36
3 3 39
op1 = 4 op1 = 3 op1 = 3 op1 = 3
op2 = 9 op2 = 36 op2 = 36 op2 = 36
S
(3,3), (3,2), (3,1), (3,0), (2,0), (1,0), (0,0)
Para la solución presentada al problema descrito en esta sección se requiere de una pila
para ir guardando las posiciones por las que se pasó y no se siguió por un posible camino a
72 CAPÍTULO 3. PILAS
partir de ahı́. Al no encontrar la salida se deshace el camino y se regresa al punto inicial del
mismo, se toma un elemento de la pila que indica el inicio de un nuevo camino. Un algoritmo
para la solución del problema es el siguiente:
/**
* Clase para encontrar la salida de un laberinto
* @author Amparo López Gaona
*/
3.3. APLICACIONES DE PILAS 73
0 1 2 3 4 5 6 7
0000 0001 0010 0011 0100 0101 0110 0111
8 9 10 11 12 13 14 15
1000 1001 1010 1011 1100 1101 1110 1111
S 12 6 12 7
8 3 8 6
8 4 2 10
E 9 1 3 11
Método 3.2. Constructor que lee del archivo pasado como parámetro primero las dimen-
siones del laberinto y luego el código para las paredes del mismo. Cada número debe estar
separado por un espacio en blanco o en lı́nea aparte. Este constructor también deja en cero
la matriz visitado para poder empezar a trabajar con ella.
/**
* Constructor que lee el laberinto de un archivo.
* @param nombre -- nombre del archivo de texto que contiene el laberinto
*/
public Laberinto (String nombreArch) throws IOException {
Scanner in = new Scanner(new File(nombreArch));
ancho = in.nextInt();
largo = in.nextInt();
74 CAPÍTULO 3. PILAS
/**
* Método para encontrar la salida del laberinto
* @return boolean -- devuelve true si hay salida y false en otro caso
*/
public boolean encontrarSalida () {
Pila pila = new Pila();
pila.push(new Punto(largo-1, ancho-1)); // Guarda la entrada
int contVisitas = 0;
while (! pila.estaVacia()) { // Mientras la pila tenga elementos
Punto pto = (Punto) pila.pop(); // Toma el elemento del tope
int x = pto.obtenerX();
int y = pto.obtenery();
if (visitado[x][y] == 0) { // Si no está visistado
visitado[x][y] = ++contVisitas; //se marca como visitado
if (pto.equals(salida))
return true; // Se llegó a la salida
guardarVecinos(x, y, pila); // se guardan sus vecinos
}
}
return false; // No se puede llegar a la salida
}
Método 3.4. El método guardarVecinos busca las celdas adyacentes a las que se puede
ir desde la celda pasada como parámetro. Para encontrarlas se utiliza una operación para
trabajar con un número a nivel de bits. El operador es el de conjunción que se representa
con un solo sı́mbolo ampersand (&), y funciona tomando cada vez un bit del entero que es
el primer operando y el correspondiente del entero que es el segundo operando, tomando
el valor uno como verdadero y el cero como falso. Ası́, por ejemplo: 1001 & 1010 devuelve
1000. En el caso del laberinto se va a realizar la operación con los números potencia de 2
para descubrir si hay pared o no de cierto lado. Al aplicar este operador con el 1 y obtener
3.3. APLICACIONES DE PILAS 75
cero significa que no hay pared en la parte inferior. Si se aplica con un 2, es decir con 10, y
obtener un cero significa que no hay pared del lado derecho, etcétera.
/*
* Método privado para guardar en la pila las posiciones vecinas a las
* que se puede acceder a partir del punto dado
* @param x -- coordenada x del punto dado
* @param y -- coordenada y del punto dado
* @param pila -- pila en la que se guardan los vecinos
*/
private void guardarVecinos (int x, int y, Pila pila) {
if ((paredes[x][y] & 1) == 0)
pila.push(new Punto(x+1, y));
if ((paredes[x][y] & 2) == 0)
pila.push(new Punto(x, y+1));
if ((paredes[x][y] & 4) == 0)
pila.push(new Punto(x-1, y));
if ((paredes[x][y] & 8) == 0)
pila.push(new Punto(x, y-1));
}
System.out.println("\nSolución:\n");
for(int i = 0; i < largo; i++){
for (int j = 0; j < ancho; j++)
System.out.print(visitado[i][j]+ " ");
System.out.println();
}
}
}
Laberinto original:
12 4 12 7
8 2 8 6
8 3 10 10
9 1 3 11
Solución:
13 0 5 6
12 0 4 3
11 0 7 2
10 9 8 1
Laberinto original:
14 13 5 6
9 5 6 14
4 6 9 6
9 1 7 11
Solución:
7 0 0 0
6 5 4 0
0 0 3 2
0 0 0 1
Método 3.6. Constructor por omisión, asigna null en tope de la pila y cero al contador de
datos.
/**
* Construye la pila.
*/
public Pila() {
tope = null;
nDatos = 0;
}
Método 3.7. El método estaVacia verifica que el tope de la pila esté en null, si es el caso
devuelve true y en caso contrario devuelve false.
/**
* Verifica que la pila esté vacı́a.
* @return true si lo está y falso en otro caso.
*/
public boolean estaVacia() {
return tope == null;
}
Método 3.8. El método vaciar asigna null al tope de la pila con lo cual se asegura que la
pila está vacı́a. También asigna cero al contador de datos.
/**
* Vacı́a una pila.
*/
public void vaciar() {
tope = null;
nDatos = 0;
}
Método 3.9. El método tamanio devuelve un entero que indica la cantidad de elementos
almacenados en la pila.
/**
* Método para conocer el tama~
no de una pila
* @return int -- cantidad de elementos en la pila
*/
public int tamanio() {
return nDatos;
}
78 CAPÍTULO 3. PILAS
Método 3.10. El método top devuelve el elemento del tope de la pila, sin alterar ésta. Si
la pila está vacı́a devuelve null.
/**
* Devuelve el elemento del tope de la pila (sin alterar ésta)
* o bien null si se encuentra vacı́a.
*/
public Object top() {
return (estaVacia()) ? null : tope.elemento;
}
Método 3.11. El método pop devuelve el elemento del tope de la pila si la pila no está vacı́a,
en otro caso devuelve null.
/**
* Extrae el elemento del tope de la pila.
* Devuelve null si la pila está vacı́a.
*/
public Object pop() {
if (estaVacia())
return null;
/**
* Agrega un nuevo elemento en la pila.
* @param x el elemento a insertar.
*/
public void push(Object dato) {
tope = new Nodo(dato, tope);
nDatos++;
}
/** Iterador para conseguir todos los elementos de la pila sin alterarla.
*/
3.4. IMPLEMENTACIÓN DEL TAD PILA 79
El tiempo que toma cada una de las operaciones sobre pilas con la implementación anterior
se muestra en la tabla 3.1. Puede observarse que el tiempo es constante en todos los métodos,
es decir, no depende del tamaño de la pila. Con lo cual se tiene que es una estructura de
datos con operaciones muy rápidas.
3.5. Ejercicios
1. Escribir dos métodos para mostrar el contenido de una pila sin alterarla. El primer
método debe mostrar los elementos del tope de la pila hacia abajo y el segundo del
fondo de la pila hacia arriba.
4. Un bibliotecario tiene el siguiente problema: tiene un estante con tres repisas. En dos
de las repisas se tienen los tomos de una enciclopedia, sólo que están desordenados. En
la primera se tienen m tomos y en la segunda n. Los tomos de la enciclopedia están
numerados del 1 al m × n. Escribir un programa para indicar el orden en que se deben
colocar los libros en la tercera repisa para que queden ordenados con la restricción de
que para sacar los libros de las repisas éstas se deben trabajar como pilas y la repisa
en la cual deben estar ordenados puede utilizarse como lista.
6. Se tienen dos pilas que contienen números enteros; los números en la primera pila
están ordenados en forma ascendente del tope hacia el fondo, y los de la segunda están
ordenados en forma descendente del tope hacia el fondo. Utilizando el TAD Pila de
este capı́tulo escribir un programa que fusione ambas pilas en una tercera ordenada
descendentemente desde el tope hacia el fondo. Restricción: el problema debe resolverse
utilizando tres pilas.
7. Escribir un programa que efectúe operaciones de suma y resta de dos números de más de
10 dı́gitos, utilizando pilas. Ayuda: cada dı́gito se almacena en una localidad de la pila
8. Se tiene una lista con los datos de los clientes de una compañı́a de telefonı́a celular,
los cuales pueden aparecer repetidos en la lista si tienen registrado más de un núme-
ro telefónico. La compañı́a para su próximo aniversario desea enviar un regalo a sus
clientes, sin dar más de uno a cada cliente. Los regalos se encuentran almacenados en
una pila de regalos. Se requiere escribir un programa que permita generar una nueva
lista donde los clientes aparezcan sólo una vez con sus regalos asignados.
9. En un almacén se guarda mercancı́a en contenedores. No es posible colocar más de n
contenedores uno encima del otro y no hay área para más de m pilas de contenedores.
Cada contenedor tiene un número y un nombre de la empresa propietaria. Escribir un
programa que permita administrar el ingreso y salida de los contenedores. Notar que
para retirar un contenedor es necesario retirar los contenedores que están encima de él
y colocarlos en otra pila.
10. La mayorı́a de los editores de texto permiten corregir lo tecleado en una lı́nea utilizan-
do la tecla de “backspace” para borrar el último carácter teclado. Para borrar la lı́nea
completa se utiliza alguna secuencia de teclas que pueden empezar con la tecla <Ctrl>,
por ejemplo, en el editor emacs con <Ctrl>A y <Ctrl>K se borra toda la lı́nea.
El ejercicio consiste en escribir un programa para simular esta caracterı́stica de los
editores. En la simulación se usará el guión (–) para borrar el último carácter y el
signo de pesos ($) para borrar desde el punto en donde se está hasta el final de la lı́nea,
y el signo de porcentaje ( %)—para borrar toda la lı́nea desde el inicio. Ejemplos de uso:
Dar una lı́nea de texto: Pai-les$Eji-e%Pa3--iliy-lla
La lı́nea editada es: Pililla
Colas
4.1. Introducción
Una cola es una estructura de datos que almacena una colección de elementos sin restricción
en cuanto al valor de los mismos, con o sin repetición, sin embargo el acceso a ellos está res-
tringido al permitir que se inserten siempre por el mismo lado (denominado final o parte
trasera de la cola) y se eliminen por otro (denominado frente de la cola). Es decir, se sacan
en el mismo orden en que entraron. En ocasiones suele referirse a ellas como estructuras
FIFO (first in, first out). (figura 4.1.).
D4 D3 D2 D1
final frente
83
84 CAPÍTULO 4. COLAS
imprimir archivos se van formando los trabajos en una cola, denominada cola de impresión, y
una forma sencilla de atenderlos es en el orden de llegada. También se utilizan para transferir
datos de manera ası́ncrona (los datos no se reciben necesariamente con la misma frecuencia
que se envı́an) entre dos procesos, por ejemplo, archivos de entrada/salida, sockets, etc.
Otro ejemplo son los buffers de lectura, aquı́ se van guardando los caracteres tan pronto
son tecleados por el usuario y se muestran en la pantalla en el mismo orden en que fueron
tecleados. Como estos hay varios ejemplos.
interface Encolable {
public boolean estaVacia();
public void vaciar();
public int tamanio();
public void agregar(Object dato);
public void eliminar() ;
public Object tomar();
public java.util.Iterator iterador();
}
• eliminar. Si la cola no está vacı́a elimina el elemento que está al inicio de la misma.
El tamaño de la cola disminuye en una unidad.
• estaVacia. Permite saber si la cola está vacı́a devolviendo true si no tiene elementos
y false en otro caso.
• vaciar. Vacı́a el contenido de una cola. Si después de llamar a este método se llama
al método estaVacia se debe obtener true.
• tomar. Devuelve el valor del primer elemento de la cola, sin alterar el estado de ésta.
4.3. APLICACIONES DE COLAS 85
Proceso en ejecución
D C B A
Siguiente proceso
Para utilizar de manera equitativa los recursos del sistema, en este caso el uso del CPU, a
cada proceso se le asigna una cantidad especifica de tiempo de CPU denominada quantum.
Si el proceso está en ejecución y se le acaba su quantum o es suspendido se coloca al final
de la cola. El siguiente proceso en la cola, el que queda al inicio, tiene ahora el derecho de
usar el CPU a lo más durante el tiempo que dure su quantum. A esta forma de trabajo se
le denomina comúnmente como planificación round-robin. En otras palabras, round-robin
es un método para seleccionar todos los elementos en un grupo de manera ordenada y
equitativa, normalmente comenzando por el primer elemento de la cola hasta llegar al último
y empezando de nuevo desde el primer elemento (figura 4.3.).
El programa está compuesto por dos clases una llamada Proceso, la cual va a simular
un proceso como un objeto con nombre, identificador, estado y tiempo requerido de CPU
para su ejecución, además de los métodos necesarios para manipular estos atributos.1 La
otra clase llamada PlanificacionDeProcesos es la clase desde la cual se va a ejecutar el
programa, solicitando al usuario la cantidad de procesos que requiere ejecutar para realizar
1
Esta clase se deja como ejercicio al lector.
86 CAPÍTULO 4. COLAS
Siguiente proceso
Tiempo n D C B A
Proceso en ejecución
Tiempo n+k A D C B
la prueba y el valor para el quantum. El tiempo para cada proceso se puede generar con un
número aleatorio o bien se puede solicitar también como dato de entrada.
Ejemplo 4.1. En el método roundrobin se implementa el algoritmo de roundrobin, éste
toma una cola de procesos y un quantum y a partir de esto organiza la ejecución de los
procesos siguiendo el algoritmo esbozado en párrafos anteriores.
/**
* método para despacho de procesos
* @param q -- quantum de cada proceso
* procesos -- Cola en que se almacenan los procesos en espera.
*/
private static void roundrobin(int q, Cola procesos) {
int tiempo = 0;
int t;
int resta;
proceso.asignarEstado(true);
procesos.agregar(proceso);
System.out.println(proceso.obtenerNombre() + "\t" + proceso.obtenerTiempo() +
"\t\t" + tiempo);
} else {
tiempo += q + resta;
proceso.asignarTiempo(0);
if (proceso.isEstado()){
System.out.println(proceso.obtenerNombre() + "\t"
+ proceso.obtenerTiempo() + "\t\t" + tiempo);
proceso.asignarEstado(false);
}
}
}
Ejemplo 4.2. A continuación un ejemplo de la salida que se puede obtener con el método
anterior, al tener 10 procesos y un quantum de 30 unidades de tiempo.
3. Si no se puede hacer el paso anterior, meter el vagón a la pista (cola) del área de
maniobras en donde el número del último vagón sea menor que el del vagón que se va
a meter. Si no existe una cola con esta caracterı́stica colocarlo en una cola vacı́a.
Si no se puede colocar en ninguna cola entonces no hay solución al problema.
4.3. APLICACIONES DE COLAS 89
/**
* Clase para acomodar los vagones de un tren en orden secuencial
* utilizando colas
* @author Amparo López Gaona
*/
public class Trenes {
Método 4.1. Constructor que recibe un arreglo de enteros con el orden inicial de los vagones
y la cantidad de pistas para maniobras.
/**
* Constructor que toma el orden de los vagones antes del reacomodo y
* la cantidad de pistas para maniobras.
* @param ordenIni -- arreglo de enteros en que se especifica el orden
inicial de los vagones.
* @param numPistas -- cantidad de pistas en el área de maniobras
*/
public Trenes (int[] ordenIni, int numPistas) {
nVagones = ordenIni.length;
nPistas = numPistas;
Método 4.2. Constructor por omisión, éste proporciona un orden inicial para un tren de
nueve vagones y trabaja con tres pistas en el área de maniobras
90 CAPÍTULO 4. COLAS
/**
* Constructor por omisión.
*/
public Trenes() {
this(new int [] {3,6,9,2,4,7,1,8,5}, 3);
}
Método 4.3. Método para acomodar los vagones del tren según el algoritmo descrito en
esta sección.
/**
* Método para acomodar los vagones del tren
* @return boolean - devuelve true si es posible acomodarlos y false
* en otro caso.
*/
public boolean acomodarVagones() {
int sgteVagonFuera = 1;
Método 4.4. El método sacarDeAreaM es un método auxiliar para sacar un vagón del área
de maniobras. Recibe el número que identifica el vagón que se desea sacar y devuelve true
si es posible hacerlo y false en otro caso.
/**
* Método para colocar un vagón en el área de maniobras
* @param - número del vagón que se desea colocar.
* @return boolean - devuelve true si es posible colocarlo en alguna
* de las pistas y false en otro caso
**/
public boolean colocarEnAreaM(int vagon) {
for (int i = 1; i < nPistas; i++)
if (pista[i].estaVacia() || vagon > ultimoVgnEnCola[i]) {
pista[i].agregar(new Integer(vagon));
ultimoVgnEnCola[i] = vagon;
System.out.println("Mueve el vagón "+ vagon + " de la entrada al "
+ "área "+ i);
return true;
}
return false; // No hubo lugar
}
1 2 3
E S E 3 4 S
1 2 5
2 3 4 5
/**
* Clase para encontrar la salida rápida de un laberinto
* @author Amparo López Gaona
*/
public class Laberinto {
private int largo, ancho; // Dimensiones del laberinto
private Punto inicio, fin; // Puntos de entrada y salida del laberinto
private int [][] paredes; // Laberinto
private int [][] camino; // Matriz para marcado de celdas
Método 4.6. Constructor que crea un laberinto a partir de la matriz dada, el punto de
entrada y el de salida. Inicializa la matriz de marcado con cero.
Método 4.7. Constructor que crea un laberinto a partir de la matriz dada en un archivo,
el punto de entrada y el de salida. En el archivo deben estar primero las dimensiones de la
matriz, luego las coordenadas del punto inicial y las del final, y por último la representación
del laberinto.
Método 4.8. Método para encontrar la salida del laberinto, primero marca los vecinos y
luego recorre el camino inverso para mostrar la salida.
Método 4.9. Método para etiquetar los vecinos, siempre que no haya pared ni se encuentre
con la salida, marca la distancia y lo agrega a la cola de pendientes para marcar posterior-
mente a sus vecinos.
Método 4.10. Método para marcar el camino para salir del laberinto. Empieza en la salida
y va retrocediendo hasta encontrar la entrada. Cada celda por la que pasa se guarda en una
pila.
/*
* Método para marcar el camino para salir del laberinto.
* @return Pila -- pila en la que está el camino de salida del laberinto.
*/
private Pila marcarCamino() {
Pila ruta = new Pila();
int distancia = camino[fin.obtenerX()][fin.obtenerY()];
Punto punto = fin;
int x = fin.obtenerX();
int y = fin.obtenerY();
boolean heAvanzado;
ruta.push(fin);
while(!punto.equals(inicio)) {
heAvanzado = false;
if ((paredes[x][y] & 1) == 0 && camino[x+1][y] == distancia -1
&& !heAvanzado) {
punto = new Punto(x+1, y);
heAvanzado = true;
}
if (!heAvanzado &&(paredes[x][y] & 2) == 0 && camino[x][y+1] == distancia-1){
punto = new Punto(x,y+1);
heAvanzado = true;
}
if (!heAvanzado && (paredes[x][y] & 4) == 0 && camino[x-1][y] == distancia-1){
punto = new Punto(x-1,y);
heAvanzado = true;
}
if (!heAvanzado && (paredes[x][y] & 8) == 0 && camino[x][y-1] == distancia-1){
punto = new Punto(x, y-1);
4.4. IMPLEMENTACIÓN DEL TAD COLA 97
heAvanzado = true;
}
ruta.push(punto);
distancia --;
x = punto.obtenerX();
y = punto.obtenerY();
}
return ruta;
}
Método 4.11. Método para mostrar la salida del laberinto, sacando todos los elementos de
la pila.
/**
* Método para mostrar la salida del laberinto
* @param Pila - pila que contiene el camino de salida encontrado
*/
public void mostrar(Pila p) {
System.out.println("El laberinto original tiene:");
for(int i = 0; i < largo; i++){
for (int j = 0; j < ancho; j++)
System.out.print(paredes[i][j]+ " ");
System.out.println();
}
/**
* Implementación del TAD Cola usando nodos ligados
98 CAPÍTULO 4. COLAS
Método 4.12. Constructor por omisión. Asigna el valor null tanto al inicio como al final
de la cola.
/**
* Constructor por omisión. Construye la cola vacı́a
*/
public Cola() {
inicio = null;
fin = null;
nDatos = 0;
}
Método 4.13. Método para determinar si una cola está vacı́a, esto es, si el inicio de la
misma tiene como valor null.
/**
* Prueba que la cola esté vacı́a.
* @return true si está vacı́a y false en otro caso.
*/
public boolean estaVacia() {
return inicio == null;
}
Método 4.14. Método para eliminar todos los elementos de la cola, lo único que hace es
que las referencias al inicio y al final de la misma tengan valor null.
/**
* Elimina todos los elementos de la cola.
*/
public void vaciar() {
inicio = fin = null;
nDatos = 0;
}
Método 4.15. El método tamanio devuelve un entero que indica la cantidad de elementos
almacenados en la cola.
4.4. IMPLEMENTACIÓN DEL TAD COLA 99
/**
* Método para conocer el tama~
no de una cola
* @return int -- cantidad de elementos en la cola
*/
public int tamanio() {
return nDatos;
}
Método 4.16. Método para agregar un elemento en la cola; éste siempre se agrega al final
de la misma.
/**
* Inserta un elemento en la cola
* @param dato - elemento que será insertado
*/
public void agregar(Object dato) {
if (inicio == null)
inicio = fin = new Nodo(dato);
else {
Nodo temp = new Nodo(dato);
fin.sgte = temp;
fin = temp;
}
nDatos++;
}
Método 4.17. Método para obtener el primer elemento de la cola. Siempre se toma el
elemento del inicio de la misma, sin alterar la cola.
/**
* Devuelve el primer elemento de la cola
* @return Object - elemento del inicio de la cola
*/
public Object tomar() {
if (inicio == null) return null; //La cola está vacı́a
return inicio.elemento;
}
Método 4.18. Método para sacar un elemento de la cola. Toma el elemento inicial, si lo
hay.
/**
* Elimina el primer elemento de la cola
100 CAPÍTULO 4. COLAS
*/
public void eliminar() {
if (inicio != null) {
inicio = inicio.sgte;
nDatos--;
}
}
Método 4.19. Método para obtener un iterador sobre los elementos de la cola. Se deja como
ejercicio su programación.
El tiempo que toma cada una de las operaciones sobre colas con la implementación anterior
se muestra en la tabla 4.1.
Debido a que se utiliza una referencia al inicio y otra al final de la cola, la complejidad de
todos los métodos presentados en la clase Cola es O(1), lo cual es insuperable.
4.5. Ejercicios
1. Añadir a la clase Cola presentada en este capı́tulo métodos para:
primer desocupado
6. Crear un TAD para manejar colas con doble salida, llamadas deques. En estas colas se
permite que los elementos sean insertados y suprimidos en ambos extremos. Por esto
en ocasiones se le denomine bicola. Este TAD puede crearse como una extensión de la
clase Cola.
La clase Deque debe contener, además de los métodos para las colas, los siguientes:
Para la programación del TAD se puede partir de cero o bien utilizar colas del TAD
Cola, la única restricción es que las operaciones descritas sean de orden constante.
Árboles
Las estructuras de datos hasta ahora vistas se distinguen entre sı́ en la forma en que permiten
introducir y retirar elementos de ellas. Estas estructuras tienen en común el hecho de que
siempre es posible conocer el elemento que está antes o después de algún elemento dado, por
eso se dice que son estructuras lineales. En este capı́tulo se presenta una estructura de datos
que los organiza imponiéndoles un orden jerárquico. Esta estructura se conoce como árbol.
En computación hay diferentes tipos de árboles, en este capı́tulo se presentan los árboles en
general, los árboles binarios, y dentro de éstos, los árboles de búsqueda y los balanceados.
También se presentan algunas aplicaciones en las que se utilizan con estructuras de datos
presentadas en capı́tulos anteriores.
5.1. Introducción
Un árbol es una colección de nodos conectados por arcos, en la cual no hay ciclos. En dicha
colección existe un nodo distinguido llamado raı́z y el resto de los nodos, si los hay, se dividen
en conjuntos ajenos llamados subárboles. En todo árbol siempre hay un único camino de la
raı́z a cualquier otro nodo. Ejemplos de árboles son: la tabla de contenido de un libro, la de los
torneos deportivos, los árboles genealógicos, la organización de archivos en una computadora.
Las diferentes relaciones que existen entre los nodos de un árbol tienen un nombre especı́fi-
co. Los nodos directamente conectados a un nodo particular son los hijos de ese nodo. Un
nodo a es padre de un nodo b si existe un enlace de a a b (en ese caso, también se dice que
b es hijo de a). Existe un solo nodo sin padres a partir del cual se forma el árbol, a éste se
le conoce como raı́z. Un nodo que no tiene hijos se conoce como hoja o nodo externo. Los
nodos que tienen padre y al menos un hijo se denominan nodos interiores. En los árboles se
usa la misma terminologı́a que en las familias para designar la relación entre nodos, ası́, los
hijos del mismo padre se llaman hermanos, los nodos tienen padres, abuelos, etc. El grado
de un nodo es el número de hijos que tiene. El grado de un hoja es cero. El grado de un
árbol es el mayor grado que tiene sus nodos.
105
106 CAPÍTULO 5. ÁRBOLES
En la figura 5.1. se presenta un árbol con una estructura jerárquica de clases en Java. En la
figura, la raı́z es el nodo etiquetado con la palabra Object, las hojas son Ahorro, Nacional,
Internacional, Cheque, DepositoException y RetiroException. Notar que a diferencia
de los árboles en el mundo real, en computación la raı́z queda arriba y las hojas abajo. Un
subárbol es el enmarcado en un cuadro con lı́neas punteadas y formado por los nodos Cuenta
(raı́z de este subárbol), Ahorro, Crédito, Cheque, Nacional e Internacional.
Object
Cuenta CuentaException
Nacional Internacional
En los árboles se utiliza término nivel. Por definición la raı́z del árbol está en el nivel 1 y
cualquier nodo está a un nivel más que el de su padre. Ası́ los hijos de la raı́z están en el
nivel 2, sus nietos en el 3, etc. Los ancestros de un nodo n son todos los nodos en los niveles
inferiores conectados a n, de manera directa o indirecta. Los descendientes de un nodo son
todos los nodos de niveles superiores conectados a él. La altura de un árbol es el número
máximo de niveles que tiene.
El árbol de la figura 5.1. tiene una altura de 4. Los ancestros de Ahorro son Cuenta y
Object. Descendientes de Cuenta son Ahorro, Crédito, Cheque, Nacional, Internacional.
Los nodos internos son Object, Cuenta, CuentaExcepcion y Crédito.
Ejemplo 5.1. En los analizadores sintácticos se utilizan árboles para revisar la sintaxis. Por
ejemplo, si se tiene la siguiente gramática para expresiones condicionales:
<proposición> ::= <selección> | <expr>
<selección> ::= if ( <exp> ) <proposición> else <proposición>
<expr> ::= <relacional> | <asignación> | identificador
<relacional> ::= <expr> < <expr>
<asignación> ::= <expr> = <expr>
proposición
selección
relacional
...
expr < expr
A B
Las hojas representan los elementos terminales (palabras reservadas, identificadores y/o
sı́mbolos) empleados en la instrucción. Los nodos interiores representan las categorı́as sintácti-
cas. El compilador entre sus tareas tiene la de construir estos árboles para cada programa y
verificar que éste cumpla con las reglas de la gramática, en cuyo caso genera el código objeto.
+ *
− / B +
A B X 2 C D
• un solo nodo, o
• un árbol binario cuya raı́z tiene a lo más dos hijos, siendo cada uno a vez un árbol
binario.
A A
B C D B C D
E F G H I J E F G H I J
Aunque no parece un árbol sı́ lo es. Al girarlo se puede ver de la manera acostumbrada,
como se muestra en la figura 5.5.
/**
* Clase de nodos para trabajar con árboles binarios.
* @author Amparo López Gaona
*/
public class NodoArbol {
5.3. IMPLEMENTACIÓN DE ÁRBOLES BINARIOS 109
E C
F G D
Método 5.1. Constructor por omisión, inicializa todos los atributos del nodo con el valor
null.
/*
* Inicializa con null el nodo creado.
*/
public NodoArbol () {
this (null, null, null);
}
Método 5.2. Constructor que inicializa el nodo con el valor recibido como parámetro y los
hijos con el valor null.
/**
* Inicializa el nodo con el valor dado como parámetro
* @param valor -- valor que tendrá el nodo
*/
public NodoArbol (Object valor) {
this (valor, null, null);
}
110 CAPÍTULO 5. ÁRBOLES
Método 5.3. Constructor que inicializa el nodo con los valores recibidos para cada uno de
sus atributos.
/**
* Inicializa el nodo con el valor dado y subárboles dados como parámetro
* @param v -- valor que tendrá el nodo
* @param izq -- raı́z del sub-árbol izquierdo
* @param der -- raı́z del sub-árbol derecho
*/
public NodoArbol (Object v, NodoArbol izq, NodoArbol der) {
valor = v;
izquierda = izq;
derecha = der;
}
}
5.3.1. Recorridos
Existen operaciones sobre árboles binarios que implican trabajar con todos los nodos del
árbol, por ejemplo: calcular la cantidad de nodos que tiene el árbol, determinar si dos árbo-
les son idénticos, hacer una copia del árbol, imprimir el árbol, etcétera. Para realizar tales
acciones se requiere visitar todos los nodos del árbol. Durante esta visita se realiza la opera-
ción deseada, la cual puede ser: contabilizar, comparar, imprimir, etcétera.
Como no se tiene estructura lineal, no es posible recorrerlo con un iterador, ya que éste
trabaja siempre con el siguiente elemento, pero en los árboles no existe tal concepto. A partir
de cada nodo se puede continuar con su hijo izquierdo y/o derecho, por lo que existen varias
formas de recorrer árboles; las comunes son las siguientes tres:
Ejemplo 5.2. Si se tiene el árbol de la figura 5.3., el resultado con los distintos recorridos
es el siguiente:
5.3. IMPLEMENTACIÓN DE ÁRBOLES BINARIOS 111
/**
* Recorrido en preorden
* @param nodo -- nodo a partir del cual se realiza el recorrido
*/
public void preorden (NodoArbol nodo) {
if (nodo != null) {
procesar(nodo.valor);
preorden(nodo.izquierdo);
preorden(nodo.derecho);
}
}
En ocasiones se requiere hacer el recorrido de un árbol por niveles. Esto se consigue exa-
minando, de izquierda a derecha, primero todos los nodos del nivel 1, luego los del nivel 2,
etcétera. Para lograr este recorrido se utiliza una cola en la cual se van guardando los nodos
visitados. Primero se inserta la raı́z y luego, en cada paso, se elimina un nodo de la cola y
sus hijos se colocan en ella.
Ejemplo 5.3. Programa para recorrer un árbol por niveles según el algoritmos explicado en
el párrafo anterior. Se implementa como un iterador, que resulta interesante, pues todo el
trabajo lo hace el método next. En el constructor se guarda, en la cola, la raı́z del árbol que
se va a recorrer.
/**
* Programa que recorre un árbol por niveles.
* @author Amparo López Gaona
* @version Abril 2011
*/
class OrdenPorNivel implements java.util.Iterator {
private Cola c = new Cola();
un subárbol, formado por los dos operandos del tope de la pila de operandos y el
operador recién extraı́do; este subárbol se almacena en la pila de operandos.
Ejemplo 5.4. Clase para generar un árbol binario a partir de una expresión aritmética según
el algoritmo descrito.
/**
* Clase para generar arboles binarios a partir de expresiones aritméticas
* @author Amparo López Gaona
* @version Abril 2011
*/
public class ArbolDeExpresiones {
Pila pOperandos;
Pila pOperadores;
final String blanco;
final String operadores;
Método 5.5. El constructor por omisión crea las dos pilas necesarias para la creación del
árbol, define los operadores aritméticos y los espacios en blanco.
Método 5.6. Método para construir un árbol para una expresión aritmética.
/** Método para construir un árbol para una expresión aritmética dada.
* @param expresión -- Cadena con la expresión aritmética
* @return NodoArbol -- nodo raı́z del árbol creado
*/
114 CAPÍTULO 5. ÁRBOLES
Método 5.7. Método privado para guardar en la pila de operandos un subárbol con una
subexpresión formada a partir de los operandos del tope de la pila de operandos y el operador
en el tope de la pila de operadores.
/*
* Método privado para almacenar en la pila un subárbol
*/
private void guardarSubArbol() {
NodoArbol op2 = (NodoArbol)pOperandos.pop();
NodoArbol op1 = (NodoArbol)pOperandos.pop();
pOperandos.push(new NodoArbol(op1, pOperadores.pop(), op2));
}
}
Puede observarse que en las pilas se almacenan diferentes tipos de datos; esto es posible
debido a que se implementó una pila genérica que guarda objetos de la clase Object y porque
toda clase definida en Java es subclase de Object.
En esta clase se pueden incluir el método para evaluar la expresión y el método para
verificar que los paréntesis estén balanceados vistos en el capı́tulo de pilas. También se
pueden incluir métodos para imprimir el árbol en sus diferentes representaciones (infija,
prefija, posfijo).
¿nada?
si no
pez ¿ruge?
si no
puma perro
(a) Si la respuesta es si, ir por el lado izquierdo del árbol para hacer otra pregunta.
(b) Si la respuesta es no, ir por el lado derecho del árbol para hacer otra pregunta.
Ejemplo 5.5. Programa que juega con el usuario a adivinar animales y va construyendo el
árbol. Se necesita el nodo raı́z del árbol y un Scanner para interactuar con el usuario.
/**
* Clase para jugar a adivinar animales
* @author Amparo López Gaona
* @version Abril 2011
*/
class AdivinaAnimal {
private NodoArbol raiz;
private Scanner in;
/**
* Método para adivinar un animal
*/
public void jugar () {
raiz = new NodoArbol("Perro");
in = new Scanner(System.in);
NodoArbol nodo = raiz;
animalNuevo (nodo);
nodo = null;
}
}
}
Método 5.9. Método privado para leer la respuesta del usuario; regresa un valor booleano
de verdadero en caso que la respuesta sea si y falso en otro caso.
/*
* Método privado para leer una respuesta del usuario sólo puede ser si o no
* @return boolean -- true si la respuesta es si y false en otro caso.
*/
private boolean respuesta () {
String resp = in.nextLine().tolower();
while(true) {
if (resp.equals("si") return true;
if (resp.equals("no") return false;
System.out.println("La respuesta debe ser si o no");
}
}
En caso de no adivinar el animal, se debe incorporar ese nuevo dato al árbol. Para ello,
se pregunta al usuario la forma de determinar de qué animal se trata, y el nodo que es una
hoja se convierte en nodo interno con dos hijos, cada uno con un animal. El nuevo animal se
coloca en el lado correspondiente de acuerdo con la respuesta a la pregunta solicitada. Por
ejemplo, con el árbol del lado izquierdo de la figura 5.7. y el intento de adivinar si se trata
de una ballena, el árbol se modifica, como se muestra en el lado derecho de la misma figura.
¿nada? ¿nada?
Método 5.10. El método animalNuevo tiene como objetivo dar de alta un nuevo animal
en el árbol. Recibe como parámetro el nodo que será el padre del animal.
118 CAPÍTULO 5. ÁRBOLES
/**
* Método para dar de alta un nuevo animal
* @param nodo -- nodo del cual se va a colgar el animal
*/
private void animalNuevo (NodoArbol nodo) {
String animalNodo = (String) nodo.valor;
System.out.println("¿Cuál es tu animal?");
try {
String nuevoA = in.nextLine();
System.out.println("Con qué pregunta, cuya respuesta sea si/no, puedo"
+ " determinar que se trata de un(a) " + nuevoA);
String pregunta = in.nextLine();
NodoArbol nodo1 = new NodoArbol(animalNodo);
NodoArbol nodo2 = new NodoArbol(nuevoA);
System.out.println("¿Para un(a) "+nuevoA+" la respuesta es si/no?");
nodo.valor = "¿"+pregunta+"?";
if (respuesta()) {
nodo.izquierda = nodo2;
nodo.derecha = nodo1;
} else {
nodo.izquierda = nodo1;
nodo.derecha = nodo2;
}
} catch (IOException e) { } // no hace nada
}
¿Qué pregunta debo hacer para determinar que es un ballena (la respuesta
debe ser Si/No)?
¿Es mamı́fero?
¿Para un ballena la respuesta es si o no?
Si
¿Quieres jugar otra vez?
3. Si se llegó a un árbol vacı́o entonces almacenar el número en una nueva posición del
árbol.
Un árbol binario de búsqueda es un árbol binario en el que para cada nodo se tiene que
los valores de su subárbol izquierdo son menores que él, y los del subárbol derecho son
mayores que él. De esta forma al hacer un recorrido en inorden se obtienen los datos en
orden ascendente. En la figura 5.8. se tiene un árbol binario de búsqueda (en adelante sólo
árbol de búsqueda) con nombres de personas. Al recorrerlo en inorden se tiene Abigail,
Adán, Adela, Agustı́n, Alberto, Alejandro, Alicia, Amparo, Andrea y Armando.
Una ventaja de usar estos árboles es que para localizar un elemento se tiene que recorrer a lo
más de la raı́z a la hoja correspondiente, lo cual toma O(log n). El árbol del ejemplo contiene
10 elementos y su profundidad es 4. Por lo tanto, para encontrar un dato o determinar que
no está se tienen que hacer como máximo cuatro comparaciones.
120 CAPÍTULO 5. ÁRBOLES
Alejandro
Agustín Amparo
5.5.1. Implementación
Para crear el TAD correspondiente a árboles binarios de búsqueda se implementará la si-
guiente interfaz:
• contiene. Regresa true si el elemento está en el árbol y false en otro caso. Este
método no cambia el estado del árbol.
• vaciar. Elimina todos los elementos del árbol. El número de nodos del árbol después
de esta operación es cero.
Clase 5.2. Clase para el TAD árbol binario de búsqueda. En esta clase se requiere un nodo
para guardar la raı́z del árbol, un contador para el número de elementos en el árbol y un
comparador para saber la relación de orden entre dos elementos.
/**
* Clase para trabajar con árboles binarios de búsqueda
* @author Amparo López Gaona
*/
public class ArbolBinarioBusqueda implements ArbolBuscable{
protected NodoArbol raiz;
private final import java.util.Comparator prueba;
private int nDatos;
Método 5.11. Constructor que recibe un objeto que implementa la interfaz Comparator
del paquete java.util para poder establecer una relación de orden entre los valores en el
árbol.
/**
* Inicializa un árbol binario de búsqueda.
* @param c objeto comparador usado para colocar elementos en secuencia.
*/
public ArbolBinarioBusqueda (Comparator c) {
prueba = c;
raiz = null;
nDatos = 0;
}
Método 5.12. Constructor por omisión. Inicializa el árbol binario de búsqueda con un
comparador para objetos de la clase Integer.
/**
* Constructor por omisión. Compara enteros.
*/
public ArbolBinarioBusqueda () {
this(new ComparadorEnteros());
}
/**
* Determina si el árbol está vacı́o.
* @return true en caso de que el árbol esté vacı́o.
*/
public boolean estaVacio () {
return raiz == null;
}
Método 5.14. Método para eliminar todos los elementos del árbol, lo único que hace es que
la raı́z tenga valor null y el número de datos sea cero.
/**
* Elimina todos los elementos de la cola.
*/
public void vaciar() {
raiz = null;
nDatos = 0;
}
Método 5.15. El método tamanio devuelve un entero que indica la cantidad de elementos
almacenados en el árbol.
/**
* Método para conocer el tama~
no de una cola
* @return int -- cantidad de elementos en la cola
*/
public int tamanio() {
return nDatos;
}
Clase 5.3. Clase privada para comparar dos objetos de la clase Integer. Se usa cuando no
se proporciona un comparador al constructor.
/*
* Clase privada para comparar dos objetos de la clase Integer.
*/
private class MiComparator implements Comparator {
public int compare(Object o1, Object o2) {
return (Integer)o1 - (Integer)o2;
}
}
5.5. ÁRBOLES BINARIOS DE BÚSQUEDA 123
Método 5.16. El método agregar permite insertar un elemento en el árbol, para ello se
compara éste con el almacenado en la raı́z, si son iguales se terminó el trabajo. En caso de
ser menor se vuelve a realizar este método, ahora con el subárbol izquierdo; si es mayor se
trabaja con el subárbol derecho. Notar que es un método recursivo, puesto que la definición
se presta para ello.
/**
* Inserta en el árbol, ignora duplicados.
* @param dato el dato a insertar
*/
public void agregar(Object dato) {
raiz = agregar(dato, raiz);
}
/**
* Método interno para agregar en un subárbol.
* @param dato elemento a agregar.
* @param nodo la raiz del árbol en donde se agregara el dato.
* @return la nueva raiz.
*/
private NodoArbol agregar(Object dato, NodoArbol nodo) {
if(nodo == null)
nodo = new NodoArbol(dato);
else if(prueba.compare(dato, nodo.valor) < 0)
nodo.izquierda = agregar(dato, nodo.izquierda);
else if(prueba.compare(dato, nodo.valor) > 0)
nodo.derecha = agregar(dato, nodo.derecha);
else ; // No hace nada con los duplicados
return nodo;
}
Método 5.17. Método para encontrar el dato con el valor menor. Éste se encuentra en
el nodo que está más a la izquierda del árbol. Se presenta una versión recursiva para este
trabajo.
/**
* Encuentra el menor elemento del árbol.
* @return el menor elemento en el árbol o nulo si está vacı́o.
*/
public Object encontrarMin() {
NodoArbol n = encontrarMin(raiz);
return (n == null) ? null: n.valor;
}
124 CAPÍTULO 5. ÁRBOLES
/**
* Método interno para encontrar el menor elemento en un árbol.
* @param t el nodo raı́z del árbol
* @return el nodo que contiene el menor elemento.
*/
private NodoArbol encontrarMin(NodoArbol nodo){
if(nodo == null)
return null;
else if(nodo.izquierda == null)
return nodo;
return encontrarMin(nodo.izquierda);
}
Método 5.18. Método para encontrar el elemento mayor. En este caso es el elemento más
a la derecha y se utiliza un procedimiento iterativo, aunque también podrı́a ser recursivo.
Para eliminar un elemento del árbol, primero se encuentra la posición del nodo que lo
contiene, si existe tal nodo; para no perder la propiedad de ser árbol de búsqueda se sustituye
el valor almacenado en dicho nodo, ya sea por el valor mayor en el subárbol izquierdo, o bien,
por el valor menor en el subárbol derecho. Por ejemplo, si se desea eliminar el nodo que tiene
el número 65 en el árbol mostrado en la parte izquierda de la figura 5.9., se sustituye éste
por el nodo con el 62, que es el valor mayor del subárbol izquierdo (parte derecha de la figura
5.9.) o puede sustituirse por el 68, que es el menor valor de su subárbol derecho.
50 50
38 65 38 62
25 60 80 25 60 80
30 53 62 68 30 53 68
Método 5.20. El método eliminar implementa el algoritmo antes descrito para suprimir
un elemento de un árbol binario de búsqueda.
126 CAPÍTULO 5. ÁRBOLES
/**
* Elimina un elemento del árbol, en caso de no encontrarlo no hace nada.
* @param dato elemento a eliminar
*/
public void eliminar(Object dato) {
raiz = eliminar(dato, raiz);
}
/**
* Método interno para eliminar de un subárbol.
* @param dato elemento a eliminar.
* @param nodo el nodo raiz del árbol.
* @return la nueva raı́z.
*/
private NodoArbol eliminar(Object dato, NodoArbol nodo) {
if(nodo == null)
return nodo; // El dato no se encuentra
if(prueba.compare(dato, nodo.valor) < 0)
nodo.izquierda = eliminar(dato, nodo.izquierda);
else if(prueba.compare(dato, nodo.valor) > 0)
nodo.derecha = eliminar(dato, nodo.derecha);
else if(nodo.izquierda != null && nodo.derecha != null) {
//Tiene dos hijos
nodo.valor = encontrarMin(nodo.derecha).valor;
nodo.derecha = eliminar(nodo.valor, nodo.derecha);
}
else // A lo más tiene un hijo
nodo = (nodo.izquierda != null) ? nodo.izquierda : nodo.derecha;
return nodo;
}
Método 5.21. El método imprimirArbol sirve para imprimir los datos de un árbol binario
de búsqueda en orden ascendente, para ello hace un recorrido de éste en inorden.
/**
* Imprime el contenido del árbol ordenado.
*/
public void imprimirArbol() {
if(estaVacio())
System.out.println("Árbol vacı́o");
else
imprimirArbol(raiz);
}
5.5. ÁRBOLES BINARIOS DE BÚSQUEDA 127
/**
* Método interno para imprimir un subárbol.
* @param nodo nodo raı́z del árbol.
*/
private void imprimirArbol(NodoArbol nodo) {
if(nodo != null) {
imprimirArbol(nodo.izquierda);
System.out.println(nodo.valor);
imprimirArbol(nodo.derecha);
}
}
El tiempo que toma cada una de las operaciones sobre árboles binarios de búsqueda con
la implementación anterior se muestra en la tabla 5.1.
espacio o tiempo. Por ejemplo, minimizar la cantidad de bodegas a alquilar para guardar
cierto tiempo algunos productos o minimizar la cantidad de vehı́culos requeridos para trans-
portar ciertos productos para su distribución. En sistemas operativos se utiliza para asignar
memoria a trabajos.
Por ejemplo, se puede suponer que se tiene un almacén con 20 objetos; el peso de cada uno
es 22, 59, 68, 77, 21, 15, 17, 45, 27, 21, 35, 5, 94, 19, 10, 24, 30, 40 y 46 kg, respectivamente, y se
necesita almacenarlos en bodegas con capacidad para 100 kg cada una. El problema consiste
en hacerlo minimizando la cantidad de bodegas utilizadas.
Este problema es NP, es decir, su solución no toma un tiempo polinomial, por lo tanto se
resuelve usando un algoritmo de aproximación. En este caso, tal algoritmo genera soluciones
que usan una cantidad de contenedores cercana al mı́nimo. Existen cuatro algoritmos de
aproximación para este problema:
1. First Fit (FF). En este caso el objeto se empaca en el primer contenedor en el cual
quepa; generalmente se recorren de izquierda a derecha los contenedores para encon-
trarlo.
2. Best Fit (BF). En este caso se considera la capacidad no utilizada del contenedor. Para
cada objeto que se desea almacenar se seleccionan los contenedores en los cuales puede
caber y se almacena en el que tiene la menor capacidad no utilizada.
3. First Fit Decresing (FFD). Este método es igual al primero, excepto que antes de
empezar a empacar los objetos se acomodan en orden decreciente de acuerdo con su
capacidad.
4. Best Fit Decresing (BFD). Este método es igual al BF en cuanto a la asignación del
contenedor, con la diferencia de que los objetos se ordenan de acuerdo con su capacidad
antes de empezar a empacarlos.
En esta sección se presenta una solución utilizando el método BF. Se trabaja con un
árbol de búsqueda en el que se almacenan los contenedores, teniendo en cuenta la capacidad
disponible de ellos. Al ir llenándolos es posible que esta capacidad se repita, ası́ que se
utilizará un árbol binario de búsqueda que acepte repetidos.
Ejemplo 5.6. Clase para crear árboles binarios de búsqueda permitiendo elementos repeti-
dos. Se implementa como una extensión de la clase ArbolBinarioBusqueda.
/**
* Clase que extiende ArbolBinarioBusqueda para permitir trabajar con
* datos duplicados.
* @author Amparo López Gaona
*/
class ArbolBinarioBusquedaR extends ArbolBinarioBusqueda {
5.5. ÁRBOLES BINARIOS DE BÚSQUEDA 129
Método 5.22. Constructor por omisión; llama al de la superclase para utilizar el comparador
de enteros.
/**
* Constructor por omisión.
*/
public ArbolBinarioBusquedaR () {
super();
}
/**
* Inicializa un árbol binario de búsqueda.
* @param c -- objeto comparador usado para colocar elementos en secuencia.
*/
public ArbolBinarioBusquedaR (java.util.Comparator c) {
super(c);
}
Método 5.24. El método agregar trabaja igual que el de la superclase, pero esta vez inserta
el nuevo nodo del lado izquierdo cuando el elemento a insertar es menor o igual que el nodo
raı́z.
/**
* Inserta en el árbol manteniendo el balance e ignorando duplicados.
* @param dato el dato a insertar
*/
public void agregar(Object dato) {
raiz = agregar(dato, raiz);
}
/*
* Método interno para agregar en un subárbol.
* @param dato elemento a agregar.
* @param nodo la raı́z del árbol en donde se agregara el dato.
* @return la nueva raı́z.
*/
private NodoArbol agregar(Object elemento, NodoArbol nodo) {
if(nodo == null) {
nodo = new NodoArbol(elemento);
nElementos ++;
} else if(prueba.compare(elemento, nodo.valor) <= 0)
nodo.izquierda = agregar(elemento, nodo.izquierda);
130 CAPÍTULO 5. ÁRBOLES
else
nodo.derecha = agregar(elemento, nodo.derecha);
return nodo;
}
Para resolver el problema de empacado se requiere tener una clase para los contenedores.
Cada contenedor debe tener un identificador, su capacidad disponible y una lista de objetos
almacenados en él (al inicio ésta debe estar vacı́a). Debido a la sencillez de esta clase se
omite su codificación.
Los objetos pueden tener toda la información necesaria para la aplicación particular, pero
deben contar con al menos un atributo para especificar la capacidad del mismo, por lo tanto
se pide que estos objetos implementen la interfaz Objeto definida como
public interface Objeto {
public int capacidad();
}
Ejemplo 5.7. La clase BinPack tiene el método de empacado. El constructor de la clase
utiliza un comparador para números enteros proporcionada en esta clase.
/** Clase para empacado usando siempre el contenedor en el que mejor
* quepa cada objeto a empacar
* @author Amparo López Gaona
* @version abril 2011
*/
public class BinPack {
ArbolBinarioBusquedaR arbol;
/**
* Método por omisión crea un árbol binario de búsqueda con duplicados
*/
public BinPack () {
arbol = new ArbolBinarioBusquedaR(new MiComparador());
}
5.5. ÁRBOLES BINARIOS DE BÚSQUEDA 131
Método 5.26. El método de empacado recibe dos parámetros, el primero es un arreglo con
los objetos que deben empacarse y el segundo es la capacidad de los contenedores.
Método 5.27. El método menorMayor es utilizado por el método empacar para encontrar el
contenedor cuya capacidad es tal que cabe el objeto que se quiere almacenar, pero también
es la menor en el cual sucede esto.
Clase 5.4. Para ubicar los contenedores en el árbol se toma en cuenta su capacidad dispo-
nible, por ello se incluye la clase interna MiComparador que implementa un comparador.
/*
* Clase para comparar la capacidad disponible de dos contenedores.
*/
private class MiComparador implements java.util.Comparator {
public int compare(Object o1, Object o2) {
return ((Contenedor)(o1)).obtenerDisponible() -
((Contenedor)(o2)).obtenerDisponible();
}
}
4
2 6
1 3 5 10
7 12
16
20
Clase 5.5. La clase NodoAvl presentada a continuación es una extensión de la clase NodoArbol.
Debido a que la altura es información muy importante, en los nodos de este tipo de árboles
se incluye. Los constructores llaman a sus equivalentes de la superclase y agregan la altura
con valor igual a cero.
/**
* Clase de nodos para arboles balanceados
* @author Amparo López Gaona
* @version abril 2011
*/
class NodoAvl extends NodoArbol{
int altura; //Hereda valor, izquierda y derecha
NodoAvl(Object valor) {
this(valor, null, null );
}
Para ilustrar la forma de creación de estos árboles se muestra en el caso en que se desea
incluir los números 1, 2, 3, 5 y 6 en ese orden, que sin balancear serı́a el caso extremo en el
que el árbol tiene una sola rama a la derecha como se muestra en la figura 5.11.
El 1 es la raı́z, por ser el primer elemento insertado. Al insertar el 2 queda del lado derecho
del 1, sin problema. Al insertar el 3, el árbol quedarı́a desbalanceado (lado izquierdo de
la figura 5.12.), ası́ que se hace una rotación a la izquierda, de tal suerte que el 2 queda
134 CAPÍTULO 5. ÁRBOLES
1
2
3
5
6
como raı́z del nuevo árbol balanceado (lado derecho de figura 5.12.). Para determinar si el
árbol está o no balanceado se toma en cuenta la altura del mismo, por eso se incluye esta
información en las siguientes figuras, separándola de la información del nodo con dos puntos.
1
2 2:1
3 1:0 3:0
Al insertar el 5 se coloca como hijo derecho del 3 y el árbol sigue balanceado (lado izquierdo
figura 5.13.). Al insertar el 6 quedarı́a como se muestra en la parte media de la figura 5.13. por
lo que se tiene que hacer una rotación a la izquierda tomando el 5 como raı́z para balancear
el árbol, obteniendo el resultado mostrado en el lado derecho de la misma figura.
En ocasiones no basta una sola rotación para dejar balanceado el árbol. Por ejemplo al
insertar el número 4 el árbol queda desbalanceado, como se muestra en la parte izquierda
de la figura 5.14. Al hacer una rotación a la derecha queda como se muestra en la parte
media de la misma figura. Es decir, no basta colocar el 3 como raı́z del nuevo subárbol, para
solucionar el problema se requiere una segunda rotación, esta vez a la izquierda, y con ello
el árbol queda como en la parte derecha de la figura 5.14., es decir, balanceado.
5.6. ÁRBOLES BALANCEADOS 135
2:2 2:2
1:0 5:1 1:0 3:2 3:2
3:0 6:0 5:1 2:1 5:1
/**
* Agregar un nodo en el árbol, ignorando los duplicados
* @param x el elemento a agregar.
*/
public void agregar(Object obj) {
raiz = agregar(obj, raiz);
}
/**
* Método interno, auxiliar, para agregar en un árbol.
* @param x elemento a agregar.
* @param t nodo raı́z del árbol.
* @return la nueva raı́z.
*/
private NodoAvl agregar(Object obj, NodoAvl n) {
if(n == null)
n = new NodoAvl(obj);
else if(cmp.compare(obj, n.elemento) < 0) {
n.izquierda = agregar(obj, n.izquierda);
if(altura(n.izquierda) - altura(n.derecha) == 2)
if(cmp.compare(obj, n.izquierda.elemento) < 0)
n = rotarIzq(n);
else { // Doble rotación sobre la izquierda
n.izquierda = rotarDer(n.izquierda);
n = rotarIzq(n);
}
}
136 CAPÍTULO 5. ÁRBOLES
Método 5.29. El método para rotar a la derecha crea un subárbol con raı́z, el hijo izquierdo
del nodo pasado como parámetro. Una vez hecha la rotación actualiza la altura de los nodos
involucrados en la misma.
/*
* Método para rotar a la derecha
* @param n -- nodo raı́z del subárbol que se va a rotar
* @return NodoAvl -- Nodo raı́z del subárbol después de la rotación
*/
private NodoAvl rotarDer(NodoAvl n) {
NodoAvl nraiz = n.derecha;
n.derecha = nraiz.izquierda;
nraiz.izquierda = n;
n.altura = max(altura(n.izquierda), altura(n.derecha)) + 1;
nraiz.altura = max(altura(nraiz.derecha), n.altura) + 1;
return nraiz;
}
Método 5.30. El método para rotar a la izquierda crea un subárbol con raı́z, el hijo derecho
del nodo pasado como parámetro. Una vez hecha la rotación actualiza la altura de los nodos
involucrados en la misma.
5.7. EJERCICIOS 137
/*
* Método para rotar a la izquierda
* @param n -- nodo raı́z del subárbol que se va a rotar
* @return NodoAvl -- Nodo raı́z del subárbol después de la rotación
*/
private NodoAvl rotarIzq(NodoAvl n) {
NodoAvl nraiz = n.izquierda;
n.izquierda = nraiz.derecha;
nraiz.derecha = n;
n.altura = max(altura(n.izquierda), altura(n.derecha)) + 1;
nraiz.altura = max(altura(nraiz.izquierda), n.altura) + 1;
return nraiz;
}
El tiempo que toma cada una de las operaciones sobre árboles binarios de búsqueda cuando
están balanceados con la implementación anterior se muestra en la tabla 5.2.
El tiempo de ejecución es logarı́tmico puesto que el árbol está balanceado.
5.7. Ejercicios
1. Crear un tipo de datos para ejemplificar las definiciones de árboles. La interfaz que
debe implementar este TAD es la siguiente:
B C D E
F I J N
G K P Q
H L M
4. Escribir un método para calcular la altura de un árbol cualquiera. Escribir dos versiones
de este método: una recursiva y otra sin recursión.
5. En el programa para adivinar animales incluir los métodos necesarios para tener la
posibilidad de leer un árbol de un archivo y al final de la sesión guardar el nuevo árbol
en el archivo. También incluir un método para imprimir un árbol binario.
6. Escribir una clase que contenga los siguientes métodos para trabajar con árboles bina-
rios:
(a) Un método recursivo que permita contar las hojas de un árbol binario.
(b) Un método que determine si dos árboles binarios A y B son idénticos o no.
(c) Un método que obtenga la copia de un árbol binario A.
(d) Un método que muestre los nodos que están en el nivel n de un árbol binario.
(e) Un método que muestre los nodos que están entre el nivel n y el m de un árbol
binario.
(f) Un método que devuelva true si el parámetro recibido es un árbol binario com-
pleto y false en otro caso.
(g) Un método para determinar si un árbol binario es de búsqueda o no.
140 CAPÍTULO 5. ÁRBOLES
(h) Un método para obtener la frontera de un árbol binario definida como la secuencia
de valores de sus hojas, tomados de izquierda a derecha.
(i) Un método que dados un árbol binario y una lista que contiene un camino, de-
termine si dicho camino existe en el árbol, teniendo en cuenta que el camino debe
comenzar necesariamente en la raı́z.
(j) Un método para podar un árbol binario dejando una copia del árbol original hasta
el nivel completo de mayor profundidad. Ejemplo:
6 6
52 13 52 13
45 26 78 96 45 26 78 96
68 21 19 41 34
83
7. Mostrar gráficamente el resultado de insertar 20, 16, 44, 57, 93, 32, 65, 19, 8 y 17 en
un árbol AVL inicialmente vacı́o.
10. Escribir un programa para generar un histograma con la cantidad de veces que se repite
cada una de las palabras contenidas en un texto almacenado en un archivo.
11. Escribir un programa que muestre las lı́neas en las que aparece cada palabra de un
texto. El texto puede ser un programa o no, y debe leerse de un archivo. En la salida
las palabras deben estar en orden alfabético.
12. En las pasadas olimpiadas se crearon tres árboles binarios de búsqueda, en cada uno
se tiene información de los medallistas. La información contenida es nombre de la
prueba, nombre del deportista y su nacionalidad. El árbol oro tiene la información de
5.7. EJERCICIOS 141
los medallistas de oro, en el árbol plata los medallistas de plata y en el árbol bronce
los medallistas de bronce. En cada árbol el criterio de ordenamiento es el nombre del
deportista. Escribir un programa para manejar esta información, en particular interesa
que dados el nombre y nacionalidad de un deportista se puede encontrar el grupo de
medallistas del mismo paı́s. También se requiere saber la cantidad y tipo de medallas
obtenidas por un deportista particular, por un paı́s particular y obtener la tabla de
posiciones de los paı́ses que obtuvieron medallas.
13. Suponer que se tiene un archivo con nombres de personas, su CURP, dirección y
teléfono. Se desea hacer un programa para ordenar los registros de las personas. La
restricción es que se requiere crear un árbol binario de búsqueda en el que en cada
nodo se tenga una estructura con los datos de las personas cuyo nombre empieza con
la misma letra, y ésta subestructura debe estar en orden ascendente.
14. Una cadena de almacenes tiene dividida su área de operaciones en tres: norte (1), centro
(2) y sur (3). Periódicamente hacen rotación de personal entre las sucursales de las tres
áreas. Se tiene un archivo en el que cada registro contiene el nombre de un vendedor,
su CURP y dos números enteros. Cada entero puede ser 1, 2, 3. El primer entero es la
zona en la se encuentra trabajando el vendedor y el segundo entero es la zona a la que
se cambiará. En el archivo los registros no tienen ningún orden. Se requiere escribir un
programa que almacene los registros en tres árboles AVL, uno por cada zona y luego
realice el intercambio de registros en los árboles para saber la nueva distribución de los
empleados.
15. Suponer que se tiene un tablero, estilo laberinto, y se desea calcular la trayectoria menos
costosa para atravesarlo. El recorrido debe empezar en la esquina superior izquierda y
terminar en la esquina inferior derecha. Sólo es posible moverse un cuadrado a la vez
en lı́nea recta horizontal o vertical, pero no diagonal. Cada cuadrado tiene un valor
positivo que representa el costo de pasar por ahı́.
Por ejemplo, el siguiente tablero tiene su entrada en el cuadrado (0,0) y salida en (2,2):
0 1 2
0 1 3 5
1 2 4 0
2 1 18 2
En este ejemplo, la trayectoria de costo menor pasa por las celdas (0,0), (1,0), (1,1),
(1,2) y (2,2) y tiene un costo de 9.
142 CAPÍTULO 5. ÁRBOLES
Escribir un programa para obtener la trayectoria de menor costo, donde una trayectoria
se define como una secuencia acı́clica de celdas. Se pueden emplear todas las estructuras
de datos necesarias, con la restricción que se debe incluir un árbol binario de búsqueda.
Capı́tulo 6
Colas de prioridad
En ocasiones no es necesario que todos los elementos de una colección se encuentren orde-
nados, basta con conocer el elemento mayor. Para aplicaciones donde la tarea más común
es localizar, dentro de una colección, el elemento con prioridad o valor mayor (menor) para
su proceso; en caso de empate en cuanto a prioridad, se toman de acuerdo con el orden de
llegada, se tiene la estructura de datos conocida como cola de prioridad, la cual se presenta
en este capı́tulo.
6.1. Introducción
Una cola de prioridad es una estructura de datos utilizada cuando se requiere que los elemen-
tos se procesen por orden de prioridad y no por el orden de llegada ni ningún otro. En otras
palabras, el orden de eliminación de elementos se determina de acuerdo con la prioridad que
tengan, a diferencia de las colas vistas en el capı́tulo 4 donde este orden está determinado por
el de llegada. De esta definición se deduce que todo elemento tiene asignada una prioridad,
aunque no necesariamente distinta. La prioridad puede ser establecida, por ejemplo, confor-
me a la importancia de la tarea o quizá al tiempo que requiere para terminar, su beneficio a
largo plazo o bien lo divertida que sea.
Las aplicaciones de la colas de prioridad incluyen aquellas en que se requiere procesar la
información de acuerdo con su urgencia. Por ejemplo, personas que llegan con una urgencia
a un hospital son atendidos aunque haya otras esperando, en general para problemas de
organización de atención a clientes o planeación de trabajos para la mejor distribución de los
recursos. En los sistemas operativos se utilizan para la ejecución de procesos que comparten
el CPU, asignando prioridad al tipo de proceso y usuario.
143
144 CAPÍTULO 6. COLAS DE PRIORIDAD
6.3.1. Ordenamiento
Uno de los problemas más trabajados en la computación es definir métodos eficientes para
ordenar datos. Una aplicación de las colas de prioridad es la creación de un método eficiente
para ordenar los elementos de un arreglo, conocido como heapsort. El algoritmo es muy
sencillo, consiste en tomar el primer elemento de la cola de prioridad (el menor) colocarlo en
un arreglo, eliminarlo de la cola y repetir este par de operaciones hasta que la cola esté vacı́a.
Ejemplo 6.1. El método ordenar es una implementación del heapsort. Devuelve un arreglo
con los datos ordenados. Al empezar se hace una copia de la cola de prioridad original para
no alterarla al extraer elementos.
/**
* Método para ordenar utilizando el algoritmo heapsort
* @return Object[] -- arreglo con los objetos ordenados.
*/
public Object[] ordenar() {
Object [] ordenados = new Object[nElementos];
Heap copia = new Heap (this);
En este caso, el algoritmo es de O(n log n), que aunque parece menos eficiente que el
algoritmo por recipientes o binsort presentado en el capı́tulo de listas, se debe recordar que
aquel algoritmo es para datos con caracterı́sticas especiales y el algoritmo aquı́ presentado
es para colecciones de datos de cualquier clase.
Este método se presenta en la sección de aplicaciones para resaltarlo, sin embargo se incluye
en la clase que implementa el TAD para las colas de prioridad.
trabajos que máquinas, por ejemplo, si se tienen 3 máquinas y 7 trabajos con 2, 14, 4, 16, 6,
5 y 3 unidades de tiempo necesarias para su respectiva realización. Una planeación posible es
formar todos los trabajos en una cola o una lista e irlos asignando a cada máquina disponible
conforme se desocupen éstas. Ası́ se coloca el trabajo 1 en la máquina 1, el 2 en la 2 y el 3 en
la 3. Cuando han transcurrido 2 unidades de tiempo se desocupa la primera máquina y en
ese punto se le asigna el trabajo 4, etcétera (figura 6.1.). En este caso, la planeación ocupa
18 unidades de tiempo.
Si se requiere que la planeación ocupe el menor tiempo posible las máquinas, para ello se van
asignando los trabajos de mayor duración a las máquinas en la primera que esté desocupada.
Ası́ se coloca el trabajo 4, que es el que toma más tiempo, en la máquina 1, el trabajo 2 en
la máquina 2 y el 5 en la 1, después de 6 unidades de tiempo se coloca el trabajo 6 en la
máquina 3, etc. En este caso la planeación queda como se muestra en la figura 6.2. y sólo
ocupa 17 unidades de tiempo.
M1 T4 (16ut)
M2 T2 (14ut) T7 (3ut)
M3 T5 (6ut) T6 (5ut) T3 (4ut) T1(2ut)
0 6 11 15 17
Figura 6.2. Planeación para tres máquinas usando una cola de prioridad.
El programa que se presenta a continuación ordena los trabajos de mayor a menor duración
utilizando el algoritmo de ordenamiento presentado en la sección anterior, luego crea una
cola de prioridad con las máquinas utilizando como elemento de comparación el tiempo en
que se desocupa cada una. Después mientras haya trabajos que realizar, toma la primera
máquina que se desocupa y le asigna un nuevo trabajo. La máquina se vuelve a colocar en
la cola de prioridad. Cada vez que se coloca un trabajo en una máquina se muestra éste y
su duración, con lo cual se va imprimiendo la planeación requerida.
6.3. APLICACIONES DE COLAS DE PRIORIDAD 147
El programa para las planeaciones hace uso de objetos de dos clases, que por su sencillez
no se presentan en esta sección. La clase Trabajo, en la cual se tiene un identificador del
trabajo y su duración con los métodos necesarios para actualizar y conocer estos datos. La
clase Maquina tiene un identificador para ella y el momento en que se desocupa. Además se
requieren dos clases que implementen la interfaz Comparator, una para comparar trabajos
y la otra para comparar máquinas.
Ejemplo 6.2. Método para organizar trabajos en la menor cantidad de máquinas posible,
para ello utiliza una cola de prioridad.
Maquina 1:
(T4,0,16)
Maquina 2:
(T7,14,17) (T2,0,14)
Maquina 3:
(T1,15,17) (T3,11,15) (T6,6,11) (T5,0,6)
6.3.3. Simulación
Suponer que se tiene el problema de determinar la cantidad de cajeros necesarios en un banco
para que los clientes no tengan que esperar demasiado en la fila ni que los cajeros estén sin
trabajo. Una forma de resolver este problema es contratar cajeros conforme a la necesidad,
la otra es simular el comportamiento del banco y estimar la cantidad de cajeros necesarios.
En esta sección se presenta la solución tomando la segunda opción.
Una simulación conducida por eventos discretos es aquella en la que los objetos en el
mundo real se modelan como objetos en la simulación con comportamiento lo más parecido
posible al real. Los eventos discretos son aquellos que ocurren en un instante del tiempo, por
ejemplo: oprimir el botón de un elevador, encender un auto, apagar un auto, la llegada de
un cliente, la salida de un cliente, prender la luz. El traslado de un sitio A a uno B no es
un evento discreto, sin embargo se puede modelar como dos eventos separados: salir de A
y llegar a B; si se asocia un valor de tiempo con cada evento discreto se puede modelar la
duración de esta actividad.
En una simulación conducida por eventos discretos los eventos se almacenan en una cola
de prioridad, de acuerdo al momento en que el evento debe ocurrir, de tal manera que el
menor elemento siempre es el siguiente evento que será modelado. Todo evento que ocurre
puede disparar otros eventos que a su vez son colocados en la cola.
A grandes rasgos la simulación trabaja como sigue:
/**
* Clase abstracta que se implementa en las clases concretas de una simulacion
* @author Amparo López Gaona
*/
public abstract class Evento implements Comparable {
protected final int hora;
/**
* Constructor que recibe la hora inicial del evento
* @param horaInicial -- hora inicial del evento
*/
public Evento (int horaInicial) {
hora = horaInicial;
}
Método 6.2. Método compareTo para determinar la relación de orden entre dos eventos de
acuerdo con la hora en que suceden.
/**
* Comparador de las horas entre eventos
* @param obj -- objeto que cuya hora se compara con el evento actual
* @return int -- entero resultado de la comparación. Positivo si el
* evento actual es posterior al parámetro; negativo si es anterior y
* cero si son iguales
*/
public int compareTo (Object o) {
Evento evento = (Evento) o;
if (hora < evento.hora) return -1;
if (hora == evento.hora) return 0;
return 1;
}
150 CAPÍTULO 6. COLAS DE PRIORIDAD
/**
* Método abstracto
*/
abstract void procesarEvento ();
}
Clase 6.2. La clase Simulacion proporciona las estructuras para las actividades de la si-
mulación, éstas son la hora en que se registra un evento y una cola de prioridad con los
eventos por ocurrir. También se tienen los métodos para registrar los eventos y realizar la
simulación. Se tienen dos constructores, uno que recibe un comparador que se pasa a la cola
de prioridad y el constructor por omisión, en el cual se proporciona un comparador.
/**
* Clase para hacer simulaciones
* @author Amparo López Gaona
*/
public class Simulacion {
private int horaActual;
private Heap eventos;
/**
* Constructor por omisión
*/
public Simulacion() {
this (new MiComparador());
}
/**
* Constructor que recibe un comparador
*/
public Simulacion(Comparator cmp) {
horaActual = 0;
eventos = new Heap(cmp);
}
Clase 6.3. Comparador por omisión para la clase Simulacion en el caso de que el usuario
no proporcione ninguno.
/**
* Comparador para ser usado en caso de que el usuario no proporcione ninguno
6.3. APLICACIONES DE COLAS DE PRIORIDAD 151
*/
private class MiComparador implements Comparator {
public int compare (Object o1, Object o2) {
Comparable oo1 = (Comparable) o2;
return oo1.compareTo (o2);
}
/**
* Método para registrar un evento en la simulacion
* @param nuevoEvento -- evento que sera registrado
*/
public void registrarEvento (Evento nuevoEvento) {
eventos.agregar(nuevoEvento);
}
/**
* Método para obtener la hora actual del evento
* @return int -- hora actual
*/
public int hora () {
return horaActual;
}
Método 6.6. Método para realizar la simulación, toma el primer elemento de la cola, ac-
tualiza la hora actual y procesa el siguiente evento.
/**
* Metodo ejecutar
*/
public void ejecutar () {
while (! eventos.estaVacia()) {
152 CAPÍTULO 6. COLAS DE PRIORIDAD
Para el problema del banco se consideran como eventos un cliente que llega al banco, un
cliente que espera en la fila hasta que alguno de los cajeros está disponible y un cajero
atendiendo a un cliente. Se requiere conocer la hora de llegada de cada cliente y el tiempo
estimado de las operaciones que va a realizar, para ello se utilizará una función generadora
de números aleatorios con cierta distribución, por ejemplo, puede utilizarse una distribución
uniforme para el tiempo de atención y una exponencial para la llegada de los clientes. Como
se especificó al inicio de la sección, se desea saber el tiempo promedio que el cliente debe
esperar, la longitud promedio de la fila y la cantidad de cajeros necesarios en el banco para
que los clientes no tengan que esperar demasiado ni les falte trabajo a los cajeros.
Ejemplo 6.4. Si se tienen dos cajeros y cuatro clientes con la siguiente información:
• Hora 13.4: El cajero 2 se desocupa. Como no hay más clientes la simulación termina.
Analizando los datos arrojados por la simulación se tiene que el tiempo de espera, en
promedio, es de 0.35, ya que las personas 1, 2 y 4 fueron atendidas inmediatamente, es decir,
no esperaron nada y la tercera persona esperó 1.4 unidades de tiempo. Lo cual es buen
tiempo de espera. Con respecto al tiempo de ocio (sin clientes) de los cajeros, se tiene que
el cajero 1 estuvo desocupado 1.5 + 2 + 0.1 = 3.6 y el segundo 2.8 + 0 = 2.8, lo que da un
promedio de 3.2.
Si se tuvieran tres cajeros la simulación darı́a el siguiente resultado: el tiempo promedio
de espera serı́a cero, pero el tiempo de ocio serı́a de 5.83.
De los eventos especificados antes se puede deducir que las clases necesarias para la si-
mulación son Cliente, Cajero y Banco. La estructura de la clase Cliente consta de un
identificador, la hora de llegada y la duración de las operaciones. También proporciona los
constructores necesarios y métodos para acceso y modificación de los atributos de la es-
tructura. La clase Cajero tiene como atributos de los cajeros su identificador y variables
necesarias para las estadı́sticas, como son el momento en que inicia su descanso, el tiempo
ocupado y los clientes atendidos por cada cajero. Ambas clases son muy sencillas y se omite
su implementación.
Clase 6.4. La clase Banco tiene una cola de prioridad para formar ahı́ a los cajeros de
acuerdo con la hora en que se desocupan, una cola para formar a los clientes que esperan
un cajero desocupado, un arreglo con los clientes que llegan al banco, un objeto para la
simulación y variables para las estadı́sticas.
/**
* Clase para la simulacion del flujo de clientes en un banco
* @author Amparo López Gaona
*/
public class Banco {
private static Heap cajeros;
private Cliente [] clientes;
private Simulacion simulacion;
private static Cola cola = new Cola() ;
private static double tiempoDeEspera;
private static int numClientes;
private final int nCajeros;
154 CAPÍTULO 6. COLAS DE PRIORIDAD
Método 6.7. El constructor de la clase Banco recibe a los clientes y la cantidad de cajeros
que tendrá el banco, inicializa todas las variables. y registra la llegada de todos los clientes.
/**
* Constructor para la simulacion de un banco
* @param clien -- Clientes que arriban al banco
* @parm numCajeros -- cantidad de cajeros que hay en el banco
*/
public Banco (Cliente[] clien, int numCajeros) {
clientes = clien;
nCajeros = numCajeros;
cajeros = new Heap(new comparadorCajero()) ;
tiempoDeEspera = 0;
numClientes = 0;
simulacion = new Simulacion();
En la clase Banco se definen los eventos de la simulación como clases privadas que extienden
la clase Evento antes definida.
Clase 6.5. La clase Llegada registra la llegada de un cliente y con el método procesarEvento
se determina el cajero que atenderá al cliente, si el cajero está desocupado se atiende al clien-
te y si no se activa el evento EsperarCajeroDesocupado para simular la espera del cliente a
que se desocupe un cajero.
/**
* Registra la llegada de un cliente.
* @param double -- hora de llegada de un cliente
* @param Cliente -- cliente que llega al banco
*/
Llegada (double hora, Cliente cl) {
super(hora);
cliente = cl;
}
6.3. APLICACIONES DE COLAS DE PRIORIDAD 155
/**
* Procesa la llegada del cliente al banco
*/
public void procesarEvento () { //Llegada cliente
if (!cajeros.estaVacia()) {
Cajero cajero = (Cajero) cajeros.obtenerPrimero();
cajeros.eliminar();
Clase 6.6. La clase AtencionCliente registra la hora en que un cliente es atendido por un
cajero y actualiza las variables para las estadı́sticas.
/**
* Registra la hora de atención al cliente
* @param double -- hora de atención al cliente
* @param Cliente -- cliente que se atiende en este momento
* @param Cajero -- cajero que atiende al cliente
*/
AtencionCliente (double hora, Cliente cl, Cajero caj) {
super(hora);
cliente = cl;
cajero = caj;
}
/**
* Método que actualiza los datos para las estadı́sticas y vuelve a
* poner disponible al cajero que atendió al cliente
*/
public void procesarEvento () {
double espera = hora - cliente.obtenerHoraDeLlegada();
156 CAPÍTULO 6. COLAS DE PRIORIDAD
if (cajeros.estaVacia()) {
simulacion.registrarEvento(new EsperaCajeroDesocupado(
hora+0.1, cliente, false));
return;
}
Cajero cajero = (Cajero) cajeros.obtenerPrimero();
cajeros.eliminar();
cola.eliminar();
6.4. IMPLEMENTACIÓN DEL TAD COLA DE PRIORIDAD 157
Clase 6.8. Clase para determinar, cuando hay dos cajeros, cuál se desocupa primero.
Una vez definida la clase Banco, lo único que queda es programar una clase que contenga
un método main, en el cual se definan los datos necesarios para la simulación, se arranque
ésta y se muestren las estadı́sticas.
La tercera opción es con un árbol binario de búsqueda. El problema es que para encontrar
el menor elemento hay que recorrer todo el lado izquierdo, tarea de orden O(log n), que no
está mal pero puede mejorarse.
Una cuarta posibilidad es utilizar un árbol binario completo con ciertas caracterı́sticas. Un
árbol binario completo es un árbol binario en el que todos los niveles del árbol, excepto el
último, están llenos y los elementos del último nivel están colocados de izquierda a derecha
sin dejar huecos entre ellos.
En la figura 6.3. se tienen dos árboles que no son completos. El primero porque no está lleno
hasta el penúltimo nivel. El segundo porque aunque el penúltimo nivel del árbol está lleno,
en el último nivel se tiene un hueco entre el nodo I y el J, pues el nodo E no tiene hijos.
A A
B C B C
D E D E F G
F G H I J K
B C
D E F G
H I J K
Entre las caracterı́sticas de un árbol binario completo está el hecho de que su altura es
siempre n debido a que está balanceado, esto sugiere que las operaciones de búsqueda,
inserción y supresión tomarán en el peor caso O(log n).
6.4. IMPLEMENTACIÓN DEL TAD COLA DE PRIORIDAD 159
Una propiedad importante de un árbol binario completo es que puede representarse efi-
cientemente en un arreglo, en el cual dado el ı́ndice de un nodo es fácil determinar su padre
y sus hijos (si los tiene). En la posición cero se tiene la raı́z del árbol. El hijo izquierdo de
cualquier nodo está en la posición 2n + 1 y el hijo derecho está en la 2n + 2. El padre de un
nodo que está en la posición par n se encuentra en la posición n/2 − 1 y si el nodo está en
una posición impar el padre está en la posición (n − 1)/2.
El arreglo correspondiente al árbol binario completo de la figura 6.4. se presenta en la
figura 6.5. Nótese que el arreglo no tiene localidades intermedias vacı́as.
A B C D E F G H I J K
0 1 2 3 4 5 6 7 8 9 10
Un heap es un árbol binario completo en el cual el valor de cada nodo es menor o igual que
el de sus hijos. Por tanto, el nodo raı́z es el menor elemento (es decir, el de mayor prioridad)
del árbol.
Se pueden tener varios heaps con el mismo conjunto de datos, porque no hay restricción
en cuanto a la ubicación de los elementos que se tiene en los árboles binarios de búsqueda.
En la figura 6.6. se muestran dos heaps para los números 1, 2, 4, 8, 7, 5, 6, 9, 10,
11. Un arreglo ordenado es un heap, pero un heap no siempre es un arreglo ordenado.
1 1
4 2 2 4
6 8 5 11 8 7 6 5
10 7 9 10 9 11
/**
* Clase para crear y trabajar colas de prioridad utilizando heaps.
* @author Amparo López Gaona.
*/
class Heap implements EncolableConPrioridad{
private Object [] elementos;
private Comparator prueba;
private int nElementos;
Método 6.8. Constructor que recibe un comparador para los elementos de la cola de prio-
ridad.
/**
* Constructor que recibe un comparador
* @param Comparator -- comparador para la prioridad de los elementos
*/
public Heap(Comparator c) {
this(c, 100);
}
Método 6.9. Constructor que recibe un comparador para los elementos de la cola de prio-
ridad y el máximo de elementos permitido en ella.
/**
* Constructor que recibe un comparador y el tama~no máximo del heap
* @param Comparator -- comparador para la prioridad de los elementos
* @param int -- tama~
no máximo del heap
*/
public Heap(Comparator c, int tam) {
prueba = c;
elementos = new Object[(tam > 0) ? tam : 100];
nElementos = 0;
}
Método 6.10. Constructor para crear una cola de prioridad a partir de un arreglo de
objetos, también se requiere de un comparador. Para hacer su trabajo llama al método
interno crearHeap que se presenta adelante.
/**
* Constructor que crea una cola de prioridad a partir de un arreglo
* @param Comparator -- comparador para la prioridad de los elementos
* @param Object [] -- arreglo de objetos que formarán el heap.
*/
6.4. IMPLEMENTACIÓN DEL TAD COLA DE PRIORIDAD 161
Método 6.11. Constructor de copia. Éste construye una copia del heap que recibe como
parámetro.
/**
* Constructor de copia
* @param Heap -- heap del cual se creará una copia
*/
public Heap(Heap hep) {
nElementos = hep.nElementos;
elementos = new Object[nElementos];
cmp = hep.cmp;
for (int i = 0; i < nElementos; i++)
elementos[i] = hep.elementos[i];
}
Método 6.12. El método para determinar si la cola de prioridad está vacı́a sólo verifica si
el número de elementos en ella es diferente de cero.
/**
* Método para determinar si la cola de prioridad está vacı́a
* @return boolean -- Devuelve true si la cola está vacı́a y false en
* otro caso
*/
public boolean estaVacia() {
return nElementos == 0;
}
Método 6.13. Método para vaciar una cola de prioridad, para ello simplemente indica que
la cantidad de elementos en ella es cero.
/**
* Método para eliminar todos los elementos de la cola de prioridad.
*/
162 CAPÍTULO 6. COLAS DE PRIORIDAD
/**
* Método para conocer la cantidad de elementos que tiene la cola
* de prioridad.
* @return int -- número de elementos en la cola de prioridad
*/
public int tamanio() {
return nElementos;
}
Método 6.15. El método para obtener el primer elemento de la cola de prioridad no altera
el estado de ésta.
/**
* Método para obtener el primer elemento de la cola de prioridad
* @return Object -- el primer elemento en la cola de prioridad
*/
public Object obtenerPrimero() {
return elementos[0];
}
Para insertar un nuevo elemento en la cola de prioridad se coloca al final del árbol. Con
esto se sigue teniendo un árbol binario completo, sin embargo puede no ser un heap si el
elemento es menor que el padre. Por lo tanto, repetidamente se intercambia el nodo que tiene
el nuevo elemento con su padre hasta tener un heap. Este método es de orden O(log n).
Por ejemplo, si se tiene la situación en que se requiere insertar el número 3 en el heap que
se muestra en la parte izquierda de la figura 6.7. se coloca como hijo del 8, y como es se
deben intercambiar. Ahora el 3 queda como hijo del 7 y como es menor se intercambian y
queda en su lugar, pues el 3 es mayor que el 2.
Método 6.16. El método agregar tiene la implementación del algoritmo descrito. Recibe
el objeto que deberá colocar como nuevo elemento en la cola de prioridad. Si el arreglo se
llena se hace crecer como en el método 1.23.
/**
* Metodo para agregar un nuevo elemento en la cola de prioridad
* @param valor -- Objeto que se va a insertar
6.4. IMPLEMENTACIÓN DEL TAD COLA DE PRIORIDAD 163
2 2 2
7 9 7 9 3 9
10 8 13 16 10 3 13 16 10 7 13 16
15 12 11 3 15 12 11 8 15 12 11 8
*/
public void agregar(Object valor) {
int posicion = nElementos; // Va agregar el dato al final
int posPadre = (nElementos -1)/2;
Object valorPadre = null;
if (posicion == elementos.length) {
crecerArreglo();
}
elementos[posicion] = valor;
if (posPadre >=0)
valorPadre = elementos[posPadre];
while((posicion > 0) && (cmp.compare(valor, valorPadre) < 0)) {
elementos[posicion] = valorPadre;
posicion = posPadre;
posPadre = (posicion -1)/2;
if (posPadre >= 0)
valorPadre = elementos[posPadre];
}
elementos[posicion] = valor;
nElementos++;
}
Notar que insertar un elemento en una cola de prioridad toma un tiempo de O(log n)
debido a que la máxima cantidad de intercambios posibles es el número de niveles del árbol,
es decir, 1+log2 (n).
En esta estructura de datos el único elemento que se puede borrar es el primero, y esto lo
hace el método eliminar, sustituyendo la raı́z por el último elemento del árbol. Sin embargo,
164 CAPÍTULO 6. COLAS DE PRIORIDAD
esto puede alterar la condición de ser un heap, con lo cual se va recorriendo el árbol hacia
abajo para encontrar su lugar vı́a el método ajustarHeap.
Por ejemplo, si se requiere eliminar la raı́z del heap mostrado en la parte izquierda de la
figura 6.8., se coloca el 8 como raı́z. Debido a que es mayor que sus hijos se intercambia con
el 3, que es el menor hijo. Como es mayor que sus hijos, se intercambia con el 7 y termina
(figura 6.8.).
2 8 3
3 9 3 9 8 9
10 7 13 16 10 7 13 16 10 7 13 16
15 12 11 8 15 12 11 15 12 11
3
7 9
10 8 13 16
15 12 11
Método 6.17. El método eliminar tiene la implementación del algoritmo para eliminar
el elemento de menor prioridad de una cola con prioridad, el cual es el único que se puede
eliminar de ésta.
El método ajustarHeap se encarga de restablecer el heap, para ello se examinan los dos
hijos del nodo que está en la posición indicada (pos). Si el menor de los hijos es mayor que
el padre se tiene un heap. En caso contrario se deben intercambiar ambos valores. Al hacer
esto, la nueva raı́z es menor que ambos elementos. Ahora es necesario continuar examinando
el subárbol cuya raı́z es el elemento donde se modificó el valor en el intercambio anterior. La
posición del hijo menor es el nuevo valor de la variable pos y el ciclo continúa. El proceso
termina cuando el valor en cuestión encuentra su ubicación (siendo el menor de los dos hijos)
o bien se llegó a un lugar sin hijos.
Método 6.18. Método interno para restablecer la propiedad de heap en un arreglo, según
lo descrito en el párrafo anterior.
/*
* Método privado para ajustar un heap
* @param pos -- posición del nodo a partir del cual va a verificar que
* se tenga un heap
* @param tamanio -- tama~ no del arreglo
*/
private void ajustarHeap(int pos, int tamanio) {
Object valor = elementos[pos];
while (pos < tamanio) {
int posHijo = pos *2 + 1;
if (posHijo < tamanio) { //Encuentra la pos del hijo menor.
if (((posHijo + 1) < tamanio) &&
cmp.compare(elementos[posHijo+1], elementos[posHijo]) <0)
posHijo++;
if (cmp.compare(valor, elementos[posHijo]) < 0) {
elementos[pos] = valor;
return;
} else {
elementos[pos] = elementos[posHijo];
pos = posHijo;
}
} else {
elementos[pos] = valor;
return;
}
}
}
Método 6.19. El método crearHeap es un método interno que crea un heap a partir de un
arreglo de objetos, para ello se llama al método ajustarHeap con la mitad de los elementos.
Se empieza desde la mitad pues de la mitad más uno todos son hojas y por definición una
hoja es un heap.
166 CAPÍTULO 6. COLAS DE PRIORIDAD
/*
* Método para crear un heap a partir de un arreglo.
* @param a -- arreglo con los objetos que se almacenaran en el heap
*/
private void crearHeap(Object[] a) {
int max = nElementos;
Este método privado se utiliza también para el constructor que recibe un arreglo de objetos.
El tiempo que toma cada una de las operaciones sobre las colas de prioridad con la imple-
mentación anterior se muestra en la tabla 6.1..
Operación Tiempo de ejecución
constructores O(1)
constructor que recibe un arreglo O(log n)
constructor que recibe un heap O(n)
agregar O(log n)
ajustarHeap O(log n)
crearHeap O(n log n)
estaVacia O(1)
eliminar O(log n)
heapsort O(n log n)
obtenerPrimero O(1)
tamanio O(1)
vaciar O(1)
Tabla 6.1. Tiempo de ejecución de los métodos de la clase Heap.
6.5. Ejercicios
1. ¿Qué es un heap y qué es una cola de prioridad?
2. Dibujar un heap en el cual se van agregando los siguientes elementos en el orden en
que aparecen listados 6, 50, 11, 25, 42, 20, 104, 76, 19, 55, 88, 2.
3. Eliminar tres elementos del heap construido en la pregunta anterior y dibujarlo para
mostrar cómo queda una vez eliminados los tres elementos.
6.5. EJERCICIOS 167
4. Dado un árbol binario completo con 15 nodos, ¿cuántos nodos habrá que mover, en el
peor de los casos, para convertirlo en un heap?
5. Agregar los métodos siguientes a la implementación del TAD EncolableConPrioridad:
(a) decrementar(p, n), el cual disminuye el valor del elemento en la posición p del
arreglo en n unidades positivas.
(b) incrementar(p, n), el cual incrementa el valor del elemento en la posición p del
arreglo en n unidades positivas.
(c) borrar(p), el cual elimina el elemento colocado en la posición p.
(d) imprimir(), el cual imprime el heap como un árbol.
6. Una cola puede implementarse usando una cola de prioridad y un contador. Cada
vez que se agrega un elemento, el contador se incrementa y se agrega al elemento. El
contador sirve como prioridad a los elementos. Implementar la interfaz Encolable del
capı́tulo 4 usando esta idea. ¿Se puede implementar una pila con el mismo enfoque?
7. La implementación de colas con prioridad con un heap en un arreglo es muy eficiente,
pero no garantiza que los elementos con la misma prioridad se extraigan exactamente
en el mismo orden en que fueron insertados. Proponer una implementación alternativa
de colas con prioridad que preserve el orden de inserción independientemente de la
eficiencia de la misma.
8. Escribir un método para encontrar el elemento mayor en un min-heap. Especificar la
complejidad del método.
9. Escribir un método para determinar si un árbol binario es un heap o no. ¿Cuál es el
orden de ejecución del método?
10. En el capı́tulo 4 se presentó una aplicación consistente en asignar tiempo de procesador
a procesos en una computadora de un sólo procesador. Resolver el mismo problema
considerando ahora que los procesos tienen una prioridad de ejecución. En este caso el
procesador se va asignando siempre al proceso que tenga la mayor prioridad y necesite
más tiempo del mismo; si el proceso no termina se vuelve a formar.
11. Suponer que se desea abrir una cafeterı́a y es necesario decidir la cantidad de sillas que
se necesitan para que no falten ni sean tantas que haya varias vacı́as. Hacer un simula-
ción del comportamiento de una cafeterı́a para poder obtener la información solicitada.
12. Hacer un programa de simulación de un banco en el cual los clientes llegan y se forman
en la caja cuya fila está más corta. Comparar tiempo de espera por parte de los clientes,
tiempo desocupado de los cajeros y número de clientes atendidos por cajero contra los
tiempos obtenidos en la simulación en donde los clientes están en una sola fila.
Capı́tulo 7
Tablas de dispersión
7.1. Introducción
Suponer que se necesita hacer un programa que constantemente busque y localice los datos
de una persona, para determinar si se tiene registro de ella o no. Los datos de cada persona
son, entre otros, el nombre y un identificador numérico de seis dı́gitos. Se tiene información
registrada de 10 000 personas.
De acuerdo con lo estudiado en capı́tulos anteriores pueden surgir varias propuestas de
solución: una serı́a colocar los datos en un arreglo, ordenarlo y utilizar búsqueda binaria. El
problema con esta solución es que es necesario hacer varias comparaciones antes de encontrar
el elemento buscado, además de la complejidad de ordenar los registros de cada persona. Otra
solución es utilizar un árbol binario de búsqueda, en cuyo caso la complejidad de la búsqueda
es O(log(n)).
Para localizar los datos con un solo acceso se pueden almacenar en un arreglo de 1 000 000
localidades y utilizar el identificador de cada persona como ı́ndice para el arreglo. Esta
solución desperdiciarı́a mucho espacio. Otra posibilidad es construir y aplicar una función al
identificador de tal manera que devuelva un número entre 1 y 10 000, y ese número utilizarlo
como ı́ndice para un arreglo de 10 000 elementos. Ésta es la función de dispersión.
169
170 CAPÍTULO 7. TABLAS DE DISPERSIÓN
Se ilustra la solución al problema con un conjunto reducido de datos. Suponer que se tienen
los siguientes 8 registros:
Una buena función serı́a calcular el residuo de la división del identificador entre 8, con lo
cual se tiene un número entre 0 y 7, y éste puede utilizarse como ı́ndice de un arreglo, como
se muestra a continuación.
Colección
de llaves
f(llave)
Tabla
x
0
1
2
.
y .
.
n−1
Una tabla de dispersión es una estructura de datos en la cual los elementos se pueden
insertar, suprimir y encontrar en un tiempo constante. Esto es inmejorable. Sin embargo,
con esta técnica no es posible determinar una relación de orden entre los elementos de la
colección, ası́ pues no se puede determinar el elemento menor ni el mayor, ni recorrerla
en un orden determinado por sus elementos. Para implementar una tabla de dispersión se
requiere un arreglo y una función de dispersión. En principio, debe asignar valores diferentes
172 CAPÍTULO 7. TABLAS DE DISPERSIÓN
a elementos diferentes. Una función de dispersión perfecta es aquella que cubre todo el rango
de valores determinados por el tamaño de la tabla.
El procedimiento para almacenar/acceder a un elemento en la tabla consiste en tomar un
elemento de la colección, aplicarle la función de dispersión y almacenarlo/recuperarlo de la
posición indicada como resultado de la función.
Las propiedades que se esperan de los métodos de una tabla de dispersión son:
• estaVacia. Devuelve true si la tabla está vacı́a y false en otro caso. Este método no
cambia el estado de la tabla.
• obtener. Si la tabla no está vacı́a, devuelve el valor almacenado, cuya llave corresponde
a la proporcionada como parámetro. En otro caso devuelve null. Este método no
cambia el estado de la tabla.
2. Folding. Involucra dividir las llaves en dos o más partes y luego combinarlas para
obtener la dirección en la tabla. Por ejemplo, para mapear la llave 25936715 en un
rango de 0 a 9999, se puede dividir el número en dos partes, 2593 y 6715, y luego
sumarlos, con lo cual se tiene el 9308, que serı́a el valor de la llave. Este método es
muy útil cuando las llaves son muy grandes.
Si la llave no es numérica puede tomarse parte de un atributo y parte de otro, por
ejemplo, la letra inicial del nombre de una persona, más algunos caracteres de su
dirección, más el número de casa, etcétera. Es rápido y sencillo y permite transformar
llaves no numéricas a valores enteros.
3. Cadenas de caracteres. Multiplicar cada carácter de una cadena por una potencia de
37 y sumarlo. Expresada formalmente esta regla queda como:
n
elemento[i] × 37i
i=0
Al final del método se pregunta si el valor calculado es negativo, porque podrı́a tenerse
un valor tan grande que se produzca un overflow y aparezca como número negativo.
En este caso no es una desventaja, al contrario, se realiza una operación más sobre los
datos.
4. Trabajar con los primeros tres caracteres de la cadena y obtener un módulo.
5. Función con corrimientos. Toma cada carácter de una cadena de caracteres y acumula
su valor multiplicándolo por 2, sólo que no utiliza la multiplicación, si no corrimientos.
Al final divide esta suma entre el tamaño de la tabla y se devuelve el residuo de esta
división.
Toda función de dispersión depende de los datos a los que se va a aplicar; en esta sección
sólo se presentaron algunas posibilidades generales.
• La más sencilla es buscar hacia las localidades con ı́ndice mayor hasta encontrar
el primer lugar vacı́o. Ejemplo:
Al intentar incluir a Ana Marı́a en la localidad 0 de la tabla mostrada en 7.4. la que
le corresponde de acuerdo con su función, se busca el primer lugar desocupado, en
este caso se tiene en la posición 2. Este método se llama direccionamiento abierto
lineal.
176 CAPÍTULO 7. TABLAS DE DISPERSIÓN
0 Ángela
1 Alberto
2 ...
3 ...
4 Andrea
5 ...
6 Alfredo
7 ...
Tabla 7.4. Tabla de dispersión.
• Doble dispersión. En este caso se tiene una segunda función de dispersión que se
utiliza sólo en caso de colisiones. Ejemplo: f(i) = i* hash2 (X) donde una buena
función es R − (x %R) con R un número primo menor que el tamaño de la tabla.
Con este enfoque, al buscar un elemento se empieza en la posición dada por la función
f (k), si el elemento no es el buscado se continúa buscando sucesivamente en la tabla
(como si fuera circular) hasta que se encuentre el elemento, se encuentre una posición
vacı́a o se vuelva a la posición proporcionada por la función. En estos dos últimos
escenarios el elemento no se encuentra en la tabla.
2. Considerar que cada elemento en la tabla es una colección denominada cubeta. Aquı́ el
agregar un nuevo elemento consta de dos pasos:
(a) Encontrar la cubeta en la que se insertará el elemento.
(b) Almacenarlo en ella.
Una función de dispersión es uniforme si a cada cubeta le corresponde la misma can-
tidad de llaves. Por ejemplo, si se tienen 11 cubetas y llaves en el rango de [0, 98],
una función uniforme es aquella que coloca aproximadamente 9 de estas llaves en cada
cubeta. Para buscar un elemento se llega a la cubeta localizada en la posición dada
por la función f (k), y ahı́ se busca el elemento.
La eficiencia de los métodos para resolver colisiones depende, en general, del factor de
carga que es la cantidad de elementos en la tabla entre el tamaño de ella. Con una buena
función el costo promedio de búsquedas es casi constante conforme el factor se incrementa de
0 a 0.7, después de esto la probabilidad de colisiones y el costo de su manejo se incrementa.
Por otro lado, conforme el factor de carga se acerca a cero, se tiene una pequeña mejora en
el costo de búsqueda a cambio de un desperdicio de memoria.
Una buena función de dispersión deberı́a minimizar las colisiones, ser rápida y fácil de
calcular usando toda la información proporcionada en la llave y tener un alto factor de carga
para un conjunto de llaves.
7.5. APLICACIONES DE TABLAS DE DISPERSIÓN 177
/**
* Método radixsort
* @param datos -- arreglo de enteros que contiene las llaves.
*/
public void radixsort(int[] datos) {
178 CAPÍTULO 7. TABLAS DE DISPERSIÓN
while(continuar) {
continuar = false;
for (int i = 0; i < datos.length; i++) {
int indice = (datos[i] / divisor) %10;
if (indice > 0) continuar = true;
cubetas[indice].agregar(new Integer(datos[i]));
}
/**
* Método para obtener el sı́mbolo de un elemento
* @return double -- sı́mbolo del elemento
*/
public String obtenerSimbolo() {
return simbolo;
}
/**
* Método para obtener un valor de dispersión para un elemento quı́mico
* @return int -- valor de dispersión del elemento
*/
public int hashCode() {
int hashC = posicion;
for(int i=0; i<simbolo.length(); i++)
hashC += (simbolo.charAt(i) -’A’);
return hashC % 103;
}
/**
* Método para obtener el nombre y sı́mbolo de un elemento
*/
public String toString() {
return nombre+ "("+simbolo+")";
}
}
Ejemplo 7.3. La clase PesoMolecular permite calcular el peso molecular de fórmulas quı́mi-
cas.
En un archivo elementos.txt se tiene para cada elemento su posición en la tabla quı́mica,
su nombre, sı́mbolo y peso molecular. Se toma el sı́mbolo como llave. Son 103 elementos
quı́micos, pero se crea una tabla con capacidad un poco mayor para minimizar las colisiones.
/**
* Clase para calcular el peso molecular de formulas quı́micas.
* Se requiere del archivo elementos.txt que tiene la información de
* cada elemento quı́mico.
* @author Amparo López Gaona
*/
public class PesoMolecular {
Dispersable elementos;
public PesoMolecular() {
elementos = new Dispersable(111);
}
7.5. APLICACIONES DE TABLAS DE DISPERSIÓN 181
try{
BufferedReader in = new BufferedReader (new FileReader("elementos.txt"));
String linea = in.readLine();
while(linea != null) {
campos = linea.split(",");
nombre = campos[0];
posicion = Integer.parseInt(campos[1]);
simbolo = campos[2];
peso = Double.parseDouble(campos[3]);
elementos.agregar(new ElementoQ(nombre, simbolo, posicion, peso));
linea = in.readLine();
}
} catch (Exception e) {
System.out.println("ERROR"+e);
}
}
Método 7.1. El método calcularPeso recibe como parámetro una fórmula y calcula su
peso molecular.
El parámetro es una cadena donde cada elemento quı́mico con la cantidad de átomos se
separa de otro por un punto. Por ejemplo H2.0. Este método extrae cada pareja, si no hay un
número se asume que es uno. Con el sı́mbolo del elemento se accede a la tabla de dispersión
y se obtiene su peso atómico, el cual se va sumando.
/**
* Método para calcular el peso molecular de una formula quı́mica
* @param formula -- cadena con la formula quı́mica
* @return double -- peso molecular de la formula recibida
*/
public double calcularPeso(String formula) {
double total = 0.0;
String[] campos = formula.split("\\.");
int pos; boolean hayDigito;
if (Character.isDigit(campos[i].charAt(pos++))){
pos--;
hayDigito = true;
}
String simbolo = campos[i].substring(0, pos);
double peso = obtenerPeso(simbolo);
String atomos = campos[i].substring(pos, campos[i].length());
while(it.hasNext()) {
el = (ElementoQ)it.next();
if (el.obtenerSimbolo().equals(simbolo))
return el.obtenerPeso();
}
System.out.println("El simbolo "+simbolo+" no está en la tabla");
return 0;
}
}
El peso de Fe es 55.85
El peso de Fe2.O3 es 159.7
El peso de Ca3.P.O4.P.O4 es 310.2
/**
* Método para asignar color a un punto
* @param color -- nuevo color del punto
*/
public void asignarColor( Color color ) {
this.color = color;
}
/**
* Método para asignar diámetro a un punto
* @param diametro -- nuevo diámetro del punto
*/
public void asignarDiametro(int diametro) {
this.diametro = diametro;
}
Método 7.8. Método para calcular el valor de dispersión de un punto. Divide entre el
tamaño de la tabla la sumas de las coordenadas y el diamétro del punto.
/**
* Método para calcular el valor de dispersión de un punto
* @return int -- valor de dispersión del punto.
*/
7.5. APLICACIONES DE TABLAS DE DISPERSIÓN 185
/**
* Clase para almacenar/recuperar puntos con color y grosor de una
* tabla de dispersión
* @author Amparo López Gaona
*/
public class Puntotes extends Frame {
private Dispersable tabla;
private Random rand;
Método 7.10. El método paint recupera los valores de la tabla de dispersión y los grafica
en un lienzo de 200 × 200.
/**
* Método para graficar los puntos recuperados de una tabla de dispersión.
*/
public void paint( Graphics g ) {
PuntoHash p;
/**
* Constructor para una tabla de dispersión del tama~
no indicado
* @param n la cantidad de cubetas en la tabla
*/
public TablaDeDispersion (int n) {
cubetas = new Lista[sgtePrimo(n)];
for (int i = 0; i < cubetas.length; i++)
cubetas[i] = new Lista();
nElementos = 0;
}
Método 7.12. Constructor por omisión para una tabla de dispersión. La crea con 101
cubetas.
/**
* Constructor por omisión para una tabla de dispersión con 101 cubetas
*/
public TablaDeDispersion () {
this(100);
}
Método 7.13. Método para verificar si la tabla de dispersión está vacı́a, para ello utiliza la
variable nElementos, y si ésta tiene valor cero significa que la tabla está vacı́a, en otro caso
no lo está.
/**
* Verifica si la tabla está vacı́a
* @return true si la tabla está vacı́a y false en otro caso
*/
public boolean estaVacia () {
return nElementos == 0;
}
/**
* Determina la cantidad de elementos en la tabla
* @return int -- cantidad de elementos en la tabla
*/
public int tamanio () {
return nElementos;
}
188 CAPÍTULO 7. TABLAS DE DISPERSIÓN
Método 7.15. Método para dejar sin elementos una tabla de dispersión. Es suficiente dar
valor de cero a la variable nElementos y limpiar cada cubeta, asignándole una lista vacı́a a
cada una.
/**
* Elimina todos los elementos de la tabla.
*/
public void vaciar () {
for (int i = 0; i < tamanio(); i++)
cubetas[i] = new Lista ();
nElementos = 0;
}
Método 7.16. Método para agregar un elemento a la tabla de dispersión.
/**
* Agrega un elemento a la tabla
* @param val objeto que se insertará en la tabla
*/
public void agregar (Object val) {
cualCubeta(val).agregar(val);
nElementos++;
}
Método 7.17. Método para determinar si un elemento está en la tabla de dispersión o no.
/**
* Determina si una tabla contiene un valor particular
* @param val -- elemento que se busca
* @return true -- si la tabla contiene un valor particular y false en
* otro caso.
*/
public boolean contiene (Object val) {
return cualCubeta(val).contiene(val);
}
Método 7.18. Método para eliminar un valor de la tabla de dispersión.
/**
* Elimina un valor de la tabla
* @param val Objeto que será eliminado de la tabla
*/
public void eliminar (Object val) {
cualCubeta(val).eliminar(val);
nElementos--;
}
7.6. IMPLEMENTACIÓN DE TABLAS DE DISPERSIÓN 189
Método 7.19. Método para obtener los elementos en la tabla que tienen la misma llave.
/**
* Devuelve los elementos que tienen la misma llave
* @param val -- llave del elemento que se busca
* @return Lista -- lista con los elementos que tienen la misma llave.
*/
public Lista obtener (Object val) {
return cualCubeta(val);
}
Método 7.20. Método privado para determinar con qué cubeta se trabajará.
/*
* Método interno para determinar en qué cubeta se realizará una
* operación.
*/
private Lista cualCubeta (Object val) {
return cubetas[Math.abs(val.hashCode()) % cubetas.length];
}
/**
* Iterador de la tabla
* @return Iterator -- que mantiene los elementos de la tabla
* @see java.util.Iterator
*/
public java.util.Iterator iterador () {
return new miIteradorHash();
}
Clase 7.2. Clase privada que implementa el iterador. Es muy interesante, pues se trata de
un iterador anidado. En el método se recorre todo el arreglo y para cada localidad crea un
iterador que corre sobre la lista incluida.
/*
* Clase privada que implementa el iterador.
*/
public miIteradorHash () {
ind = 0;
itTabla = cubetas[0].iterador();
}
/**
* Método interno para verificar si un número es primo.
* @param n -- número que se quiere verificar que sea primo.
* @return boolean -- true si el número es primo y false en otro caso.
*/
private boolean esPrimo(int n) {
if (n == 2 || n == 3)
return true;
for(int i = 3; i * i <= n; i += 2) {
if(n % i == 0)
return false;
}
return true;
}
La complejidad de los métodos del TAD tabla de dispersión con cubetas según la imple-
mentación presentada en esta sección se muestra en la tabla 7.6.
El constructor es de orden lineal debido a que se crean n listas. Los métodos de complejidad
m se refieren a la cantidad de elementos en la cubeta que con una buena función de dispersión
debe ser cercana a 1, es decir, pueden considerarse de orden constante.
192 CAPÍTULO 7. TABLAS DE DISPERSIÓN
Método 7.24. Constructor para una tabla de dispersión del tamaño especificado.
/**
* Crea una tabla de dispersión del tama~
no especificado
* @param tam -- cantidad inicial de elementos permitida
*/
public TablaDeDispersionA (int tam) {
elementos = new Object[sgtePrimo(tam)];
nElementos = 0;
}
Método 7.25. Constructor por omisión para una tabla de dispersión. La crea con 101
cubetas.
/**
* Crea una tabla de dispersión para 100 elementos
* @param tam -- cantidad inicial de elementos permitida
*/
public TablaDeDispersionA () {
this(100);
}
/**
* Verifica si la tabla está vacı́a
7.6. IMPLEMENTACIÓN DE TABLAS DE DISPERSIÓN 193
/**
* Determina la cantidad de elementos en la tabla
* @return int -- cantidad de elementos en la tabla
*/
public int tamanio () {
return nElementos;
}
Método 7.28. Método para dejar sin elementos una tabla de dispersión.
/**
* Elimina todos los elementos de la tabla.
*/
public void vaciar () {
for (int i = 0; i < elementos.length; i++)
elementos[i] = null;
nElementos = 0;
}
/**
* Agrega un elemento a la tabla
* @param val objeto que se insertará en la tabla
*/
Método 7.30. Método para determinar si un elemento está en la tabla de dispersión o no.
/**
* Determina si una tabla contiene un valor particular
* @param val -- elemento que se busca
* @return true -- si la tabla contiene un valor particular y false en
* otro caso.
*/
public boolean contiene (Object val) {
int indice = Math.abs(val.hashCode()) % elementos.length;
int indice = indiceIni;
/**
* Iterador de la tabla
* @return Iterator -- que mantiene los elementos de la tabla
* @see java.util.Iterator
*/
/*
* Clase privada que implementa el iterador.
*/
7.7. Ejercicios
1. Suponer que en un arreglo se tienen 31 números enteros distintos en orden ascendente.
2. Suponer que el tablero para el juego del gato se representa como un arreglo de enteros
donde se almacenan sólo tres posibles valores 0 para casilla vacı́a, 1 para la equis y 2
para el cı́rculo. Suponer que se tiene la siguiente función para los tableros.
¿Es una buena función de dispersión para cerca de 5 000 cubetas? Considerar que hay
19 683 tableros diferentes. Justificar la respuesta.
3. Escribir una función de dispersión para almacenar objetos de la clase Intervalo en una
tabla de dispersión. La clase tiene enteros para indicar el valor menor del intervalo y el
superior, además de los métodos para manipularlos. Suponer que todos los intervalos
están contenidos en el intervalo [0, 10]. La función deberá distribuir los valores de
acuerdo con el tamaño de la tabla.
4. Escribir un programa que permita detectar faltas de ortografı́a. Para ello se debe leer
un archivo con las palabras bien escritas. Crear una tabla de dispersión para esas
palabras, para agilizar la detección de una falta buscando una palabra leı́da contra la
tabla diccionario. El programa sólo debe reportar el error.
5. Escribir un programa para verificar la autenticidad de la contraseña correspondiente a
un usuario. El programa deberá solicitar un nombre de usuario y una contraseña, ésta
se debe buscar en una tabla de dispersión y enviar un mensaje indicando si es correcta
o no. Ejemplos:
7.7. EJERCICIOS 197
Login: maria
Password: mmariia
¡¡Password correcto!!
Login: jorge
Password: sksksks
¡¡Password incorrecto!!
7. Escribir un programa para determinar la cantidad de veces que aparece cada palabra
en un texto. El resultado debe aparecer en orden alfabético. Por ejemplo, con el texto
averigua 1
en 2
las 2
los 2
palabras 3
...
8. Escribir un programa que permita almacenar en una tabla de dispersión los datos de los
empleados en una compañı́a. De cada empleado se tiene su nombre, RFC, departamento
y sueldo. Utilizar como llave el RFC. Suponer que hay un máximo de mil empleados
y no se permite más del 13 % de colisiones. Utilizar ambas implementaciones vistas en
este capı́tulo y calcular cuántos accesos se requieren, para cada una, en promedio, para
localizar a un empleado determinado.
10. Escribir un programa para manejar una tabla de identificadores para programas en
Java. El programa debe poder localizar los identificadores, indicando para cada iden-
tificador, el número de lı́nea en que se declara, el tipo de dato que le corresponde a ese
identificador el número de lı́nea en que se utiliza y el método o clase a la que pertenece.
En este caso, se tiene la restricción de que sólo es posible declarar datos al inicio de
los métodos y clases.
Apéndice A
Recursión
En este caso se define f (x) en términos de f (x−1). Aunque se define el cálculo en términos
de sı́ misma eventualmente se llega al fin, porque se aplica la misma función a un valor
distinto, en este caso uno menor. Por ejemplo, f (3) = 2 ∗ f (2) + 3 ∗ 3, ası́ que para calcular
f (3) es necesario primero calcular f (2) = 2 ∗ f (1) + 2 ∗ 2, para ello se necesita calcular
f (1) = 2 ∗ f (0) + 1 ∗ 1 y finalmente f (0) = 0, al regresar sustituyendo los valores de f (0), f (1)
y f (2) se tiene que f (3) = 21.
Esta fórmula escrita en Java queda:
public int f(int x) {
return (x <= 0) ? 0 : 2*f(x-1) + x*x;
}
199
200 APÉNDICE A. RECURSIÓN
calculoRecursivo(3) = calculoRecursivo(3/3 + 1) + 3 - 1;
calculoRecursivo (2) = calculoRecursivo (2/3 + 1)+ 1;
calculoRecursivo (1) = calculoRecursivo(1/3 + 1) + 0;
calculoRecursivo(1) ...
2. El caso general, que vuelve a llamar al algoritmo con un caso más pequeño del mismo.
Una tarea muy común en programación es buscar elementos dentro de una colección de
datos. La forma más sencilla de hacerlo es comparar el dato buscado con cada uno de los
elementos de la colección en forma secuencial. El orden de este algoritmo es O(n), porque en
el peor de los casos se tienen que comparar todos los elementos para descubrir que el dato
no está en la colección.
En caso de que la colección esté ordenada puede usarse un algoritmo más rápido, deno-
minado búsqueda binaria, para hacer las búsquedas. El algoritmo consiste en comparar el
elemento de la mitad del arreglo con el buscado, si ambos valores son iguales se termina
la búsqueda puesto que el elemento está en la colección. Si el elemento buscado es menor,
entonces se sabe (porque el arreglo está ordenado) que se encuentra en la primera mitad
del arreglo, en otro caso se encuentra en la mitad superior del arreglo. Este proceso de ir
dividiendo el arreglo de búsqueda en mitades se repite hasta encontrar el elemento, o bien,
determinar que el elemento buscado no se encuentra.
/**
* Método para localizar un dato en un arreglo ordenado
* @param datos -- arreglo de enteros en donde está el espacio de búsqueda
* @param buscado -- elemento a buscar
* @return int -- posición del elemento encontrado o -1 si no está
*/
Un algoritmo tiene complejidad log(n) si toma un tiempo constante dividir el tamaño del
problema en una fracción. El logn (x) es aproximadamente igual al número de veces que x
puede ser dividido entre n. Ası́ el log2 (x) es, aproximadamente, igual al número de veces que
x puede ser dividido entre 2. Se dice que es aproximado porque la función logaritmo tiene
un valor fraccionario que se ignora en el análisis de algoritmos.
El cuerpo del ciclo de la búsqueda binaria es de orden O(1). Falta determinar cuántas
veces se repite. Las iteraciones empiezan con sup - inf = n-1 y terminan cuando esta
diferencia es mayor o igual a 1. Cada vez, esta diferencia se reduce en la mitad. Ejemplo si la
diferencia es de 1024, en la siguientes iteraciones será: 512, 64, 32, 16, 8, 2, 1, 0, −1. Por tanto,
el algoritmo es de O(log2 (n)).
Otra forma de escribir este algoritmo, aunque no se gana en eficiencia, es de manera
recursiva.
/**
* Método recursivo para localizar un dato en un arreglo ordenado
* @param datos -- arreglo de enteros en donde está el espacio de búsqueda
* @param inicio -- posición inicial para la búsqueda
* @param fin -- posición final para la búsqueda
* @param buscado -- elemento a buscar
* @return int -- posición del elemento encontrado o -1 si no está
*/
public int busquedaBinaria(int [] datos, int inicio, int fin, int buscado) {
int mitad = (inicio + fin)/2;
• Colocar la segunda reina en un lugar en que no pueda ser atacada por la primera.
• Colocar la tercera reina en un lugar en que no pueda ser atacada por la primera ni por
la segunda reinas.
2. Intentar la siguiente selección hasta que se tenga éxito o no haya más posiciones:
A.1. BÚSQUEDA CON RETROCESO 203
No es conveniente utilizar una matriz para representar el tablero porque complica la re-
visión de casillas ocupadas y esta es la operación más frecuente. Se debe elegir una repre-
sentación que facilite esta revisión tanto como sea posible. Cada reina debe estar en una
columna diferente y que la elección de una posición para la i-ésima reina está restringida a
la i-ésima columna. Por lo tanto, la i es el ı́ndice de la columna y el proceso de selección es
para colocarla en el renglón j.
En la diagonal de derecha a izquierda todas las localidades tienen la misma suma de sus
coordenadas (i, j), por eso el rango de valores para esta suma es de 2 a 16. La otra diagonal
tiene la propiedad que la diferencia entre i y j es constante, aquı́ el rango va de −8 a 8.
Como consecuencia de lo anterior, en lugar de utilizar una matriz para representar el
tablero, se utilizan cuatro arreglos: el arreglo columna para especificar en cuál columna hay
una reina. Los otros tres arreglos son de booleanos para indicar cuál diagonal y cuál renglón
están desocupados.
/**
* Programa para colocar reinas en un tablero de ajedrez sin que se ataquen
* unas a otras.
* Objetivo: ilustrar la técnica de backtracking.
* @version: Adaptación del algoritmo de Niklaus Wirth por Amparo López Gaona
*/
class Reinas {
private int [] columna; //columna[i] posición de la reina en la columna i.
private boolean [] renglonDesocupado; //si renglonDesocupado[j] = true
// no hay reina en el renglón j
private boolean [] diagonalDIDesocupada; //si diagonalDIDesocupada[k] == true
//ninguna reina ocupa la diagonal k de der-izq
private boolean [] diagonalIDDesocupada; //si diagonalIDDesocupada[k] == true
// ninguna reina ocupa la diagonal k de izq-der.
final int tamanio;
boolean respuesta;
Método A.1. Constructor que recibe la cantidad de reinas que se van a colocar en un
tablero, dependiendo de esta cantidad es el tamaño del tablero. La cantidad mı́nima de
reinas es 4.
/**
* Constructor que recibe la cantidad de reinas que se van a colocar
* @param n -- entero con la cantidad de reinas
*/
204 APÉNDICE A. RECURSIÓN
public Reinas(int n) {
if (n < 4) n = 4;
tamanio = n;
respuesta = false;
columna = new int[tamanio];
renglonDesocupado = new boolean[tamanio];
diagonalDIDesocupada = new boolean[tamanio*2-1];
diagonalIDDesocupada = new boolean[tamanio*2];
Método A.2. El método intentar trata de colocar recursivamente cada reina, empezando
por la primera. Cada vez que coloca una reina se llama a sı́ mismo con la siguiente reina para
colocarla. Si no puede colocar la reina restablece el estado en que estaba el tablero antes de
la llamada e intenta colocarla en otra posición. Esto es el retroceso o backtracking.
Método A.3. El método colocarReina marca en el tablero los lugares en los que no puede
colocar otra reina a partir de que se colocó una reina en la posición (i, j).
/**
* Marca los lugares peligrosos para otras reinas, si se coloca ésta
* en la posición (i,j)
*/
private void colocarReina(int i, int j) {
columna[i] = j;
renglonDesocupado[j] = false;
diagonalDIDesocupada[i+j] = false;
diagonalIDDesocupada[i-j+tamanio-1] = false;
}
Método A.4. El método quitarReina deshace el trabajo realizado por el método colocarReina,
es decir, quita la marcas de peligro que se tenı́an al colocar a una reina en la posición (i, j).
Método A.5. El método resolverReinas trata de colocar las reinas, a partir de la primera,
llamando al método intentar. Si colocan todas, muestra la solución y en caso contrario avisa
que no tiene solución el problema.
/**
* Método para resolver el problema de colocar n-reinas en un tablero de n*n
*/
public void resolverReinas() {
intentar(0);
if (respuesta) {
System.out.println("La solución es ");
for (int i=0; i < tamanio; i++)
System.out.print(columna[i]+" ");
System.out.println();
} else System.out.println("No hay solución ");
}
Método A.6. Método que crea un objeto de la clase Reinas e intenta colocar las que se
deseen.
206 APÉNDICE A. RECURSIÓN
Algoritmos de ordenamiento
B.1. Burbuja
El algoritmo más popular, que no el más eficiente, para ordenar es el conocido como algoritmo
de la burbuja. Este algoritmo recorre varias veces el arreglo que se desea ordenar, en cada
recorrido va comparando dos elementos adjuntos y si no están en el orden adecuado los
intercambia. Recorre varias veces el arreglo hasta que no haya intercambios, lo que significa
que ya está ordenado.
El algoritmo de la burbuja se implementa con dos ciclos anidados, en el ciclo interno se
comparan los elementos uno contra otro para colocar el elemento mayor en la parte baja
del arreglo. Cada iteración reduce la cantidad de veces que se tiene que hacer la iteración
interna. Al final de cada iteración interna, el elemento mayor se coloca en su posición.
207
208 APÉNDICE B. ALGORITMOS DE ORDENAMIENTO
Para calcular el orden de ejecución de este algoritmo, se toma en cuenta que el ciclo interno
se realiza n − 1 veces la primera vez, en la segunda n − 2, etc., hasta hacerlo una sola vez. Es
decir, se realiza n(n + 1)/2 = (n2 + n)/2. Por otro lado, el cuerpo del ciclo interno toma un
tiempo constante en su ejecución. Por tanto, el orden del algoritmo es O((n2 +n)/2) = O(n2 ).
B.2. Inserción
A diferencia del algoritmo de la burbuja, con este algoritmo se van ordenando subarreglos,
primero los dos primeros datos, luego los tres primeros, luego los cuatro primeros, etc.,
tomando un elemento y buscando su ubicación dentro de cada subarreglo.
/**
* Algoritmo de inserción para ordenar datos
* @param datos -- arreglo de datos enteros que se desea ordenar
*/
void insercion (int [] datos) {
for (int i = 1; i < datos.length; i++) {
int elemento = datos[i];
int j = i-1;
while (j >= 0 && elemento < datos[j]) {
datos[j+1] = datos[j];
j--;
}
datos[j+1] = elemento; // Coloca el elemento en su posición
}
}
El ciclo externo se ejecuta n−1 veces, el ciclo interno puede terminar pronto, pero en el peor
de los casos debe intercambiar todos los elementos (esto ocurre cuando el arreglo está en orden
inverso). Por tanto en el peor caso, las iteraciones internas se realizan 1 + 2 + 3 + ... + (n − 1)
veces, es decir n(n − 1)/2 veces. Por tanto el algoritmo es de orden O(n2 ).
/**
* Clase que implementa el algoritmo del quicksort para ordenamiento
*/
class QuickSort {
private int[] datos;
/**
* Constructor que recibe un arreglo
* @param a -- arreglo de enteros que se desea ordenar
*/
public QuickSort(int[] a) {
datos = a;
}
/*
* Método privado para colocar el pivote para ordenar datos
* @param inicio -- ı́ndice a partir de donde se recorre el arreglo
* @param fin -- ı́ndice hasta donde se recorre el arreglo
* @param pos -- posición del pivote
*/
private int pivote(int inicio, int fin, int pos) {
int izq = inicio +1;
int der = fin;
Método B.2. Método privado para intercambiar dos datos del arreglo.
/**
* Método para ordenar un arreglo de datos
* @param inf -- ı́ndice inferior del arreglo
* @param sup -- ı́ndice superior del arreglo
*/
public void quickSort(int inf, int sup) {
if (inf >= sup) return; // El arreglo ya está en orden.
int indicePivote = (inf+sup)/2; // Toma el elemento de la mitad como pivote
Para calcular la eficiencia del algoritmo se considera el pivote en el centro del arreglo, con
lo cual cada vez se trabaja con la mitad de elementos. La primera llamada recursiva es con
dos arreglos de la mitad de elementos, para cada una se hacen dos llamadas con dos arreglos
de la mitad de la mitad de elementos, etc. Esto lleva a tener un algoritmo de O(log n) para la
parte del pivote, y como esto se realiza n veces, se tiene el algoritmo es de orden O(n log n).
Apéndice C
Este apéndice contiene una recopilación de las guı́as de estilo seguidas en los programas
de este libro, recomendadas por la gente de Sun para organizar y dar formato al código
fuente de los programas en Java. La documentación completa se encuentra en la dirección
http://www.oracle.com/technetwork/java/codeconv-138413.html
– Cada archivo debe contener una clase o interfaz y el orden en que los elementos
deben aparecer en el archivo es:
∗ Comentario de inicio que incluya el nombre del programa, el objetivo, autor
y versión.
∗ Instrucciones import.
∗ Declaración de la clase o interfaz.
– Comentario de inicio.
– Encabezado de la clase.
– Variables estáticas.
– Variables de instancia.
– Métodos. Primero los constructores.
Nombres de identificadores.
211
212 APÉNDICE C. NORMAS DE ESTILO EN JAVA
Modificadores de variables.
Declaraciones.
Alineación (indentación).
Comentarios.
El programa javadoc
El programa javadoc tiene como propósito generar documentación para los programas es-
critos en Java. Para obtener esta documentación el programa javadoc busca los comentarios
escritos entre los sı́mbolos /** y */.
La documentación que genera son documentos escritos en HTML, para que puedan ser
vistos a través de cualquier navegador. Esta documentación queda legible, ordenada y con-
sistente para todas las clases.
En este apéndice se describen las marcas permitidas dentro de los comentarios para
javadoc y utilizadas en este libro. La documentación completa se encuentra en la dirección
http://www.oracle.com/technetwork/java/javase/documentation/index-137868.html
Las marcas utilizadas en el libro son:
• @author nombre. Para especificar el autor del programa. De esta marca puede haber
más de una en un programa, una por cada autor.
• @see referencia. Para especificar que en el código de esa clase se hace referencia a
objetos de otras clases.
• @throws clase descripción. Para especificar la clase de excepción que se puede disparar
en ese método y en qué situación.
215
216 APÉNDICE D. EL PROGRAMA JAVADOC
Para utilizar esta herramienta, la clase debe estar precedida de la palabra public. Desde
el sistema operativo se debe teclear la instrucción:
javadoc nombreDePrograma.java.
con lo cual se genera una serie de archivos con la documentación, en particular uno con el
mismo nombre de la clase y extensión html.
En la primera parte del documento .html se resalta la palabra class, si la documentación
es para una clase y si se trata de una interfaz está resaltada la palabra interface. Si estos
archivos están en un paquete, la documentación empieza con esta información aunque con
letra más pequeña que las palabras antes descritas.
En la segunda parte de la documentación se tiene el nombre de la clase y se presenta un
árbol con la jerarquı́a de clases de donde desciende la clase en cuestión, empezando por la
clase Object. Luego se especifica las interfaces que implementa.
En la tercera parte está el encabezado, en Java, de la clase, el comentario que se incluyó para
la misma y la indicación de ver otras clases utilizadas en la clase que se está documentando.
El autor y la versión no aparecen a menos que el el documento se hubiera generado con la
siguiente instrucción:
javadoc -version -author CuentaCrédito.java
En la siguiente parte de la documentación se encuentran las variables protegidas, ya sean
de la superclase o bien las definidas en esta clase.
En la siguiente parte de la documentación se tiene un resumen de cada uno de los cons-
tructores de la clase. Luego se incluye una tabla que en la primera columna tiene el tipo de
valor que devuelve el método y en la segunda la firma y abajo de ella el comentario acerca
del propósito del método. La tabla tiene tantos renglones como métodos tenga la clase. Cada
método aparece subrayado, porque en la siguiente sección se tiene más información acerca
de los métodos y se puede ir a ella directamente a través de esta liga.
La siguiente sección contiene una lista con los métodos que hereda de cada una de sus
superclases, incluyendo todos los métodos de la clase Object. Finalmente se tiene el detalle
de cada método, en el cual se incluye su firma, los parámetros que recibe y el tipo de valor que
devuelve. A estas descripciones se puede llegar desde los enlaces mencionados anteriormente.
Este formato se sigue para todas las clases e interfaces que utilicen la forma de comentarios
y etiquetas requeridas por el programa javadoc.
Apéndice E
La clase StreamTokenizer
En este apéndice que presenta una recopilación de los métodos de la clase StreamTokenizer
utilizada en varios ejemplos del libro.
La clase StreamTokenizer permite extraer elementos, denominados tokens, de un flujo
de datos. Los elementos que puede reconocer son identificadores, números, cadenas entre
comillas y varios estilos de comentarios.
El constructor de esta clase recibe un flujo de lectura que puede ser de cualquier subclase
de la clase abstracta Reader.
El método nextToken extrae el siguiente elemento del flujo y devuelve una constante que
especifica el tipo de elemento extraı́do:
1. TT EOL indica que se ha llegado al final de una lı́nea.
2. TT EOF indica que se ha llegado al final del archivo.
3. TT WORD indica que el elemento leı́do es una palabra. En este caso almacena la palabra
en el atributo sval.
4. TT NUMBER indica que el elemento leı́do es un número, en cuyo caso lo almacena en el
atributo nval.
Otros métodos que se tienen en la clase StreamTokenizer son:
217
218 APÉNDICE E. LA CLASE STREAMTOKENIZER
219
Índice alfabético
221
222 ÍNDICE ALFABÉTICO
FIFO, 83 ordenamiento
función de dispersión, 170, 171 binsort, 40
uniforme, 176 burbuja, 207
perfecta, 172 en recipientes, 40
heapsort, 145
heap, 159 inserción, 208
heapsort, 145 quicksort, 208
interfaz radix sort, 177
Apilable, 60 pila, 59
ArbolBuscable, 120 prueba cuadrática, 193
Conjuntable, 2 prueba lineal, 193
Dispersable, 172
EncolableConPrioridad, 144 recorrido en inorden, 110
Encolable, 84 recorrido en postorden, 110
Iterator, 11 recorrido en preorden, 110
Listable, 34 recorrido por niveles, 111
iterador, 11 recursión, 199
caso base, 199
LIFO, 59
lista, 33 simulación, 148
con 2 referencias, 51 subárbol, 105
ligada, 44
llave, 170 tabla de dispersión, 171
TAD, 2
max-heap, 159 árbol binario de búsqueda, 120
min-heap, 159 con repetidos, 128
cola, 84
nodo, 44 cola de prioridad, 144
ancestro, 106 conjunto, 2
cabecera, 46 heap, 159
descendiente, 106 lista, 34
externo, 105 pila, 60
grado de un, 105 tabla de dispersión, 186
hijo, 105 tipo abstracto de datos (TAD), 2
hoja, 105 tipo de datos, 1
interior, 105 tope de una pila, 60
padre, 105
notación infija, 67
notación O grande, 16
notación postfija, 67
notación prefija, 67
Estructuras de datos con con Java
editado por la Facultad de Ciencias
de la Universidad Nacional Autónoma de México,
se terminó de imprimir el 20 de octubre de 2017
en los talleres de Impresos Vacha S. A. de C. V.
José María Bustillos No. 59. Col. Algarín
C.P. 52170. Metepec. Estado de México.