4.5.8 Estructuras auto-referenciadas
§1 sinopsis
Las estructuras se utilizan con frecuencia como elementos de estructuras de datos tipo árbol y lista
( 1.8). En estos casos, un conjunto de
objetos del mismo tipo, están relacionadas entre sí mediante punteros contenidos en ellos mismos, de forma que basta conocer la
raíz del árbol o principio de la lista, para poder acceder a todo el conjunto. En ocasiones, si tales listas son doblemente
enlazadas, es posible entrar en cualquier nodo y recorrer la totalidad del conjunto en cualquier sentido. Esta es la razón del
apelativo "auto-referenciadas".
§2 Como ejemplo, construiremos un programa que acepte caracteres por el teclado y construya un árbol binario
( 1.8b) cuyos elementos contengan el
carácter introducido y estén ordenados según su valor ASCII. En la Fig. 1 se muestra gráficamente el resultado de introducir los
caracteres: b, D, g, A, E y k.
El programa acepta caracteres indefinidamente (mientras exista memoria suficiente, o se pulse ESC). Después de la introducción de cada nuevo elemento, se muestra ordenadamente la totalidad del árbol.
#include <iostream.h> // Ejemplo de creación de árbol binario
struct base {
// declara tipo de estructura a utilizar
char let;
// para almacenar carácter
struct base* izq; // puntero izquierdo
struct base* der; // puntero derecho
} *rz, *aptr;
// rz puntero al nodo raíz; aptr puntero auxiliar
int incluir(char letra, struct base* puntero);
void inorden (struct base* puntero);
char acepta (void); // aceptar datos por teclado
void main(void) { // =========================
char c;
while ( (c = acepta()) != 27) { // Bucle principal
if (incluir(c, rz)) break;
inorden(rz);
}
}
char acepta (void) { // Introducir datos por teclado
char c;
cout << "\n Pulse un carácter + [CR] ";
while (1) {
c = getchar();
if (c == 10) continue; // 10 == New Line
return c;
}
}
int incluir(char letr, struct base* ptr) { // añadir elemento
if (rz == NULL) { // 1o. solo la primera vez!!!
rz = (struct base*) malloc(sizeof(base));
if (rz == NULL) {
cout << "NO hay memoria suficiente!!" << endl; return 1;
}
rz->let = letr;
rz->izq = rz->der = NULL;
return 0;
}
if (letr == ptr->let) return 0; // 2o. El carácter ya existe
if (letr < ptr->let) { // 3o.
if (ptr->izq == NULL) { // enlace libre: incluir
aptr = (struct base*) malloc(sizeof(base));
if (aptr == NULL) {
cout << "NO queda
suficiente memoria" << endl; return 1;
}
aptr->let = letr;
aptr->izq = aptr->der = NULL;
ptr->izq = aptr;
return 0;
}
if (incluir(letr, ptr->izq)) // ocupado: seguir buscando
return
1; // falla la inserción
}
if (letr > ptr->let) { // 4o.
if (ptr->der == NULL) { // enlace libre: incluir
aptr = (struct base*) malloc(sizeof(base));
if (aptr == NULL) {
cout << "NO queda suficiente memoria" << endl; return 1;
}
aptr->let = letr;
aptr->izq = aptr->der = NULL;
ptr->der = aptr;
return 0;
}
if (incluir(letr, ptr->der)) // ocupado: seguir buscando
return
1; // falla la inserción
}
return 0;
}
void inorden (struct base* ptr) { // Recorrer árbol
if (ptr == NULL) return;
inorden(ptr->izq);
cout << " - " << ptr->let;
inorden(ptr->der);
}
Comentario
La primera parte declara la estructura, base, que será utilizada en cada nodo; contiene un carácter para alojar el introducido por teclado, y los dos punteros que necesitan los elementos de los árboles binarios. Además se definen dos punteros-a-base; uno de ellos, rz, apuntará desde el primer momento al nodo raíz; el otro, aptr, es un puntero auxiliar que se necesita en la función incluir.
Además de main, el programa solo tiene tres sencillas funciones: incluir, que incluye cada nuevo elemento en el árbol con el carácter pulsado; inorden, que recorre el árbol ordenadamente mostrando en pantalla los caracteres, y acepta, que simplemente captura los datos del teclado.
La función main consiste en un bucle que acepta indefinidamente caracteres del teclado (mientras no se pulse la tecla Escape); inserta en el árbol el carácter introducido, y finalmente muestra la totalidad del árbol hasta el momento. El proceso se termina si por alguna razón (por ejemplo, falta de memoria) falla el proceso de insertar el carácter, en cuyo caso la función incluir devuelve 1.
La función acepta no merece ningún comentario; aunque quizás se podría haber afinado un poco más para no aceptar
secuencias de escape (caracteres no imprimibles
3.2.3e); simplemente letras mayúsculas, o minúsculas, dígitos, etc. Puesto que se ha utilizado la
función getchar, es necesario pulsar también Intro con cada inserción.
Puede sorprender la extremada simplicidad de la función inorden; esta función recursiva recorre la totalidad del árbol mostrando de forma ordenada el carácter contenido en cada elemento. Es de destacar que en realidad la función:
void recorrido (struct base* ptr) {
if (ptr == NULL) return;
recorrido(ptr->izq);
recorrido(ptr->der);
}
recorrería la totalidad del árbol pasando por todos los nodos. Para recorrerlo en las formas preorden y postorden
( 1.8b), habría que sustituir
inorden por las funciones que se indican a continuación. Observe que la diferencia es pequeñísima entre las tres;
simplemente la posición del la sentencia que muestra el carácter en pantalla.
void preorden (struct base* ptr) { // recorrido preorden
if (ptr == NULL) return;
cout << " - " << ptr->let;
preorden(ptr->izq);
preorden(ptr->der);
}
void postorden (struct base* ptr) { // recorrido postorden
if (ptr == NULL) return;
postorden(ptr->izq);
postorden(ptr->der);
cout << " - " << ptr->let;
}
La función incluir, que crea cada nuevo nodo del árbol con el carácter introducido, es recursiva (como muchas de
las que tratan con árboles) y muy sencilla, pero merece algún comentario:
El cuerpo del primer if, solo se ejecuta la primera vez, cuando incluir es invocada desde main después de
introducido el primer carácter, y el puntero rz tiene todavía su valor de inicialización (NULL
4.2.1). Este valor previo
para rz y aptr es proporcionado directamente por el compilador en el momento de la declaración de estas variables
globales. Este bloque se encarga de la creación del nodo raíz (en adelante, durante todo el programa rz señala a dicho
nodo). A este respecto, obsérvese que incluir siempre es invocada desde main con el valor rz como argumento,
es decir, el proceso de inclusión se inicia siempre empezando por la raíz del árbol.
En este bloque hay que resaltar las sentencias encargadas de asignar memoria para el nuevo elemento. Estas sentencias se repiten cada vez que se crea un elemento nuevo (en los if 3º y 4º), y contienen un mecanismo de control que avisa si la memoria disponible se ha agotado:
ptr = (struct base*) malloc(sizeof(base));
if (ptr == NULL) {
cout << "NO hay memoria suficiente!!" << endl; return 1;
}
El manual de la Librería Estándar nos señala que a la función malloc hay que pasarle un entero con el tamaño del bloque
de memoria que queremos reservar -en nuestro caso sizeof(base)-, y que devuelve un puntero a la zona de memoria asignada o
un NULL si falla en el intento (cosa que aprovechamos). Observe que al valor malloc(sizeof(base)) le aplicamos un
"casting" ( 4.9.9) antes de
asignarlo a ptr; de lo contrario se obtendría un error.
Nota: también se podría utilizar el operador new
( 4.9.20), más moderno que
malloc; las sentencias anteriores serían entonces:
if ((ptr = new(base)) == NULL) {
cout << "NO hay memoria suficiente!!" << endl; return 1;
}
Cualquiera que fuese la función utilizada para crear los nuevos elementos, hay que considerar que tanto new como
malloc reservan espacio del montón. En un programa real en el que se construyeran árboles como el presente, a fin
de evitar pérdidas de memoria cuando ya no fuesen necesarios, deberían tenerse en cuenta las observaciones respecto a la
persistencia de este tipo de objetos (
1.3.2).
El segundo if simplemente no hace nada, pero acepta la entrada como válida. Ocurre cuando el carácter ya existe
previamente en el árbol (se ha repetido). El cuerpo de este bloque podría modificarse fácilmente. Por ejemplo, para incluir un
contador que señalara cuantas repeticiones se han pulsado de cada tecla. Para esto, en el diseño de la estructura base
incluiríamos un campo numérico que inicializaríamos a cero e incrementaríamos con cada repetición.
Sugerencia: en este caso también podríamos definir sendas variables globales: total y repet, que mostraran el total de elementos en el árbol y el total de repeticiones. Sus valores se actualizarían fácilmente en la función inorden, o después de cada entrada en la propia función incluir.
El tercero y el cuarto if son los encargados de la creación de los nuevos nodos después de creado el nodo raíz. Cuando llega a este punto, el nodo raíz ya existe, el árbol es ya más o menos grande y la invocación se ha realizado desde main, o se trata de una de las múltiples recursiones posibles. Mediante estas recursiones, incluir trepa (aquí deberíamos decir desciende) por el árbol siguiendo los enlaces izquierdos si el carácter a incluir es menor que el de los nodos que se va encontrando y a la inversa si es mayor. Cuando encuentra un nodo terminal adecuado, con el enlace izquierdo o derecho libre (respectivamente), solicita memoria; rellena los datos del nuevo nodo y lo cuelga del nodo terminal encontrado, cuyo enlace izquierdo o derecho se actualiza.
El nodo recién incluido es ahora terminal; sus dos enlaces están a cero y contiene el nuevo carácter. En este momento la función termina devolviendo el valor 0 (finalización con éxito), y el control vuelve a main, donde seguirá el bucle mediante la invocación de inorden...