Toda la información que se maneja dentro de un computador se encuentra almacenada en su memoria, que en términos simples es una secuencia de caracteres (bytes) en donde se encuentran las instrucciones y datos a los que se accede directamente a través del procesador del computador.
Los sistemas o métodos de organización de datos que permiten un almacenamiento eficiente de la información en la memoria del computador son conocidos como estructuras de datos. Estos métodos de organización constituyen las piezas básicas para la construcción de algoritmos complejos, y permiten implementarlos de manera eficiente.
En el presente capítulo se presentan las estructuras de datos básicas como son arreglos, listas enlazadas y árboles, con las cuales se implementarán posteriormente los tipos de datos abstractos.
Un arreglo es una secuencia contigua de un número fijo de elementos homogéneos. En la siguiente figura se muestra un arreglo de enteros con 10 elementos:
En Java un arreglo se define como:
tipo[] nombre = new tipo[n_elem];
donde tipo corresponde al tipo de los elementos que contendrá el arreglo (enteros, reales, caracteres, etc..), nombre corresponde al nombre con el cual se denominará el arreglo, y n_elem corresponde al número de elementos que tendrá el arreglo. Para el caso del ejemplo presentado, la declaración del arreglo de enteros es:
int[] arreglo = new int[10];
Para acceder a un elemento del arreglo se utiliza un índice que identifica a cada elemento de manera única. Los índices en Java son números enteros correlativos y comienzan desde cero, por lo tanto, si el arreglo contiene n_elem elementos el índice del último elemento del arreglo es n_elem-1. El siguiente código muestra como se puede inicializar el arreglo del ejemplo, luego de ser declarado:
arreglo[0]=80; //el primer indice de los arreglos en Java es 0 arreglo[1]=45; arreglo[2]=2; arreglo[3]=21; arreglo[4]=92; arreglo[5]=17; arreglo[6]=5; arreglo[7]=65; arreglo[8]=14; arreglo[9]=34; //el ultimo indice del arreglo es 10-1 = 9
También se puede declarar e inicializar el arreglo en una sola línea:
int[] arreglo={80, 45, 2, 21, 92, 17, 5, 65, 14, 34};
Una ventaja que tienen los arreglos es que el costo de acceso de un elemento del arreglo es constante, es decir no hay diferencias de costo entre accesar el primer, el último o cualquier elemento del arreglo, lo cual es muy eficiente. La desventaja es que es necesario definir a priori el tamaño del arreglo, lo cual puede generar mucha pérdida de espacio en memoria si se definen arreglos muy grandes para contener conjuntos pequeños de elementos (Nota: en Java es posible hacer crecer el tamaño de un arreglo de manera dinámica).
Un puntero es una variable que almacena la dirección de memoria de otra variable, es decir, almacena el valor del lugar físico en la memoria en donde se encuentra almacenada dicha variable. Si se imagina que la memoria del computador es un gran arreglo de bytes, la dirección de memoria correspondería al índice de los casilleros de dicho arreglo, que es precisamente lo que se almacena en el puntero.
En algunos lenguajes de programación, por ejemplo C, es posible declarar explícitamente punteros para distintos tipos de variables, e incluso es posible realizar aritmética de punteros para realizar operaciones de manera muy eficiente, a cambio de "oscurecer" el código del programa y con una alta probabilidad de cometer errores de programación díficiles de detectar.
En Java no se puede declarar punteros de manera explícita ni tampoco realizar aritmética de punteros. Por lo tanto es imposible en Java tener un puntero a cualquiera de los tipos primitivos: enteros, reales, caracteres y booleanos. Los strings y arreglos no son tipos primitivos en Java.
Una variable de referencia, o simplemente una referencia, es una variable que almacena la dirección de memoria en donde se ubica un objeto. Nótese que si bien la definición es prácticamente idéntica a la de puntero, la diferencia radica en que una referencia sólo puede apuntar a objetos residentes en memoria, lo cual excluye a los tipos primitivos. A partir de esta definición se puede concluir que toda variable en Java, que no sea de tipo primitivo, es una referencia.
Por ejemplo, todas las clases en Java heredan de la clase Object. Una instancia de ésta clase se declara como:
Object aux=new Object();
La variable aux es una referencia a un objeto de la clase Object que permite saber la ubicación de dicho objeto dentro de la memoria, información suficiente para poder operar con él. Intuitivamente, la referencia es como una "flecha" que nos indica la posición del objeto que apunta:
Una lista enlazada es una serie de nodos, conectados entre sí a través de una referencia, en donde se almacena la información de los elementos de la lista. Por lo tanto, los nodos de una lista enlazada se componen de dos partes principales:
class NodoLista
{
Object elemento;
NodoLista siguiente;
}
La referencia contenida en el nodo de una lista se denomina siguiente, pues indica en dónde se encuentra el siguiente elemento de la lista. El último elemento de la lista no tiene nodo siguiente, por lo que se dice que la referencia siguiente del último elemento es null (nula).
La siguiente figura muestra un ejemplo de una lista enlazada cuyos elementos son strings:
La referencia lista indica la posición del primer elemento de la lista y permite acceder a todos los elementos de ésta: basta con seguir las referencias al nodo siguiente para recorrer la lista.
NodoLista aux=lista;
aux=aux.siguiente;
Siguiendo con el ejemplo anterior, para insertar un nuevo nodo justo delante del nodo referenciado por aux se deben modificar las referencias siguiente del nodo aux y del nodo a insertar.
NodoLista nuevo=new NodoLista(...); //"nuevo" es la referencia del nodo a insertar en la lista nuevo.siguiente=aux.siguiente; aux.siguiente=nuevo; //Notese que no es lo mismo realizar los cambios de referencia //en un orden distinto al presentado, puesto que en ese caso //se "pierde" la lista desde el nodo siguiente a aux
El procedimiento presentado a continuación es un ejemplo de cómo se programa el recorrido de una lista enlazada. Se supondrá que los objetos almacenados en cada nodo son strings:
void recorrido(NodoLista lista)
{
NodoLista aux=lista;
while (aux!=null)
{
System.out.println(aux.elemento);
aux=aux.siguiente;
}
}
Para invertir el orden de la lista, es decir, que el último elemento de la lista ahora sea el primero, que el penúltimo elemento de la lista ahora sea el segundo, etc..., modificando sólo las referencias y no el contenido de los nodos, es necesario realizar una sola pasada por la lista, y en cada nodo visitado se modifica la referencia siguiente para que apunte al nodo anterior. Es necesario mantener referencias auxiliares para acordarse en donde se encuentra el nodo anterior y el resto de la lista que aún no ha sido modificada:
void invertir(NodoLista lista)
{
NodoLista siguiente=lista;
NodoLista anterior=null;
while(lista!=null)
{
siguiente=lista.siguiente;
lista.siguiente=anterior;
anterior=lista;
lista=siguiente;
}
}
La implementación vista de los nodos también se conoce como lista de enlace simple, dado que sólo contiene una referencia al nodo siguiente y por lo tanto sólo puede recorrerse en un solo sentido. En una lista de doble enlace se agrega una segunda referencia al nodo previo, lo que permite recorrer la lista en ambos sentidos, y en general se implementa con una referencia al primer elemento y otra referencia al último elemento.
Una lista circular es aquella en donde la referencia siguiente del último nodo en vez de ser null apunta al primer nodo de la lista. El concepto se aplica tanto a listas de enlace simple como doblemente enlazadas.
En muchas aplicaciones que utilizan listas enlazadas es útil contar con un nodo cabecera, tambien conocido como dummy o header, que es un nodo "falso", ya que no contiene información relevante, y su referencia siguiente apunta al primer elemento de la lista. Al utilizar un nodo cabecera siempre es posible definir un nodo previo a cualquier nodo de la lista, definiendo que el previo al primer elemento es la cabecera.
Si se utiliza un nodo cabecera en una lista de doble enlace ya no es necesario contar con las referencias primero y último, puesto que el nodo cabecera tiene ambas referencias: su referencia siguiente es el primer elemento de la lista, y su referencia anterior es el último elemento de la lista. De esta forma la lista de doble enlace queda circular de una manera natural.
Un árbol se define como una colección de nodos organizados en forma recursiva. Cuando hay 0 nodos se dice que el árbol esta vacío, en caso contrario el árbol consiste en un nodo denominado raíz, el cual tiene 0 o más referencias a otros árboles, conocidos como subárboles. Las raíces de los subárboles se denominan hijos de la raíz, y consecuentemente la raíz se denomina padre de las raíces de sus subárboles. Una visión gráfica de esta definición recursiva se muestra en la siguiente figura:
Los nodos que no poseen hijos se denominan hojas. Dos nodos que tienen el padre en común se denominan hermanos.
Un camino entre un nodo n1 y un nodo nk está definido como la secuencia de nodos n1, n2, ..., nk tal que ni es padre de ni+1, 1 <= i < k. El largo del camino es el número de referencias que componen el camino, que para el ejemplo son k-1. Existe un camino desde cada nodo del árbol a sí mismo y es de largo 0. Nótese que en un árbol existe un único camino desde la raíz hasta cualquier otro nodo del árbol. A partir del concepto de camino se definen los conceptos de ancestro y descendiente: un nodo n es ancestro de un nodo m si existe un camino desde n a m; un nodo n es descendiente de un nodo m si existe un camino desde m a n.
Se define la profundidad del nodo nk como el largo del camino entre la raíz del arbol y el nodo nk. Esto implica que la profundidad de la raíz es siempre 0. La altura de un nodo nk es el máximo largo de camino desde nk hasta alguna hoja. Esto implica que la altura de toda hoja es 0. La altura de un árbol es igual a la altura de la raíz, y tiene el mismo valor que la profundidad de la hoja más profunda. La altura de un árbol vacío se define como -1.
La siguiente figura muestra un ejemplo de los conceptos previamente descritos:
Un árbol binario es un árbol en donde cada nodo posee 2 referencias a subárboles (ni más, ni menos). En general, dichas referencias se denominan izquierda y derecha, y consecuentemente se define el subárbol izquierdo y subárbol derecho del arbol.
En este caso, la implementacion del nodo de un árbol binario es como sigue:
class NodoArbolBinario
{
Object elemento;
NodoArbolBinario izq;
NodoArbolBinario der;
}
Los nodos en sí que conforman un árbol binario se denominan nodos internos, y todas las referencias que son null se denominan nodos externos.
Propiedad 1:
Si se define i = número de nodos internos, e = número de nodos externos, entonces se tiene que:
Demostración: inducción sobre i (ejercicio).
Propiedad 2:
Sea n = número de nodos internos. Se define:
Demostración: inducción sobre n (ejercicio).
Propiedad 3:
¿Cuántos árboles binarios distintos se pueden construir con n nodos internos?
| n | bn |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
¿bn?
Por ejemplo: b4 = b0*b3 + b1*b2 + b2*b1 + b3*b0 = 5 + 2 + 2 + 5 = 14.
Este tipo de ecuaciones se puede resolver y la solución es la siguiente:
La serie de numeros que genera bn se conoce como números de Catalan. Asintóticamente:
La siguiente figura muestra un ejemplo de un árbol de expresiones matemáticas. En un árbol de expresiones las hojas corresponden a los operandos de la expresión (variables o constantes), mientras que los nodos restantes contienen operadores. Dado que los operadores matemáticos son binarios (o unarios como en el caso del operador signo -), un árbol de expresiones resulta ser un árbol binario.
Un árbol de expresiones se puede evaluar de la siguiente forma:
Existen tres formas principales para recorrer un árbol binario en forma recursiva. Estas son:
Por ejemplo, al recorrer el árbol de expresiones anterior en preorden se obtiene:
Al recorrer el árbol en inorden se obtiene:
Al recorrer el árbol en postorden se obtiene:
La expresión que se obtiene con el recorrido en postorden se conoce como notación polaca.
En un árbol general cada nodo puede poseer un número indeterminado de hijos. La implementación de los nodos en este caso se realiza de la siguiente manera: como no se sabe de antemano cuantos hijos tiene un nodo en particular se utilizan dos referencias, una a su primer hijo y otra a su hermano más cercano. La raíz del árbol necesariamente tiene la referencia a su hermano como null.
class NodoArbolGeneral
{
Object elemento;
NodoArbolGeneral hijo;
NodoArbolGeneral hermano;
}
Nótese que todo árbol general puede representarse como un árbol binario, con la salvedad que el hijo derecho de la raíz es siempre null. Si se permite que la raíz del árbol tenga hermanos, lo que se conoce como bosque, entonces se tiene que el conjunto de los bosques generales es isomorfo al conjunto de los árboles binarios. En efecto, las propiedades vistas en los árboles binarios se siguen cumpliendo en los árboles generales.