ÉPOCA II. ENERO 1993
TÉCNICAS DE INTELIGENCIA ARTIFICIAL: ESTRUCTURAS DE DATOS
© Warlord
Hoy trataremos un tema muy interesante y de enorme aplicación práctica como
son las estructuras de datos. En particular hablaré de las listas y de los árboles binarios.
LISTAS DOBLEMENTE ENLAZADAS:
Como ya sabréis, una lista es un conjunto de datos almacenados sencuencialmente ... es decir, algo así:
---- ----
| |->-| |->- ......
---- ----
En cada nodo podemos guardar toda la información que queramos (nombre, teléfono, dirección ...). Es decir, básicamente en cada nodo de la lista podemos guardar dos campos: Uno que sea el que guarda la información propiamente
dicha y otro que sea un puntero a la dirección del siguiente elemento de la
lista. Sin embargo a veces resulta útil utilizar otro puntero que apunte al
elemento ANTERIOR en la lista, pues en caso de perder accidentalmente la información de uno de ellos, podemos utilizar el otro para reconstruir la lista. Es el caso de las listas doblemente enlazadas.
Como creo que esta estructura es bastante fácil de entender, me limitaré a
dar el source de rigor ...
/*Warlord, Julio 1988*/
struct direc {
char nombre[40]; /*ejemplo de campo info*/
char calle[40];
char ciudad[20];
struct direc *sig;
struct direc *ante;
}info;
/* crear una lista doblemente enlazada. Se devuelve un puntero al primer
elemento, dado que es posible que se inserte un nuevo elemento al
principio de la lista*/
struct direc *dl_insert(i,top) /*almacenamiento ordenado*/
struct direc *i; /*nuevo elemento*/
struct direc *top; /*comienzo de la lista*/
{
struct direc *ant,*p;
if (ultimo=NULL){
i->sig=NULL;
i->ante=NULL;
ultimo=i;
return i;
}
p=top /*principio de la lista*/
ant=NULL;
while(p){
if(strcmp(p->nombre,i->nombre)<0){
ant=p;
p=p->sig;
}
else{
if(p->ante){
p->ante->sig=i;
i->sig=p;
i->ante=p->ante;
p->ante=i;
return top;
}
i->sig=p; /*nuevo primer elemento*/
i->ante=NULL;
p->ante=i;
return i;
}
}
ant->sig=i; /*ponerlo en el final*/
i->sig=NULL;
i->ante=ant;
ultimo=i;
return ppio;
}
ÁRBOLES BINARIOS:
¿Qué es un árbol binario?... bueno, creo que su nombre lo dice todo: Es una
estructura binaria en forma de árbol. Esto es:
-----
| | <------ NODO RAIZ
/-----\
/ \
/ \
----- -----
| | | | <----------PRIMER NIVEL
/-----\ -----\
/ \ \
----- ----- -----
| | | | | | <-----SEGUNDO NIVEL
----- ----- ----- (NODOS TERMINALES)
Este ejemplo es un árbol muy sencillito. Tiene sólo dos niveles. 2 nodos en
el primer nivel y 3 en el segundo. Creo que ya lo habréis entendido.Un árbol
binario es una estructura que comienza con un nodo(llamado "raíz" del árbol)
y a partir del cual se derivan otros nodos secundarios (las ramas del árbol)
Generalmente, cada nodo tiene dos ramas, una izquierda y otra deracha,
aunque puede tener todas las que queramos.
La inmensa mayoría de la inmensa minoría que esté leyendo este artículo
pensará ... ¿y a mí esto para qué me sirve?. Veamos, hay muchas estructuras
en la práctica que son en forma de árbol. Por ejemplo, los directorios forman estructura de árbol:
- C
DF0: - DEVS .system configuration
-PRINTERS
.epsonx
- S .startup-sequence
- SOURCES
Supongamos que queremos hacer un comando que busque un determinado archivo
en nuestro directorio. Si tenemos 3 o 4 directorios es fácil. ¿Pero y si
tenemos cientos?.
Volviendo al tema de los juegos de estrategia, supongamos que tenemos 20
países, cada país está dividido en 10 provincias y en cada provincia hay 3
ciudades. ¿Cómo manejamos esta información?. Fácilmente si la estructuramos
como un árbol ...
NODO RAIZ
/ | | | \ \ \
PAIS 1 ........... PAIS 20
/ | | \ / | | \
PROV.1 ... PROV.5 ..........
/ | \
CID.1 ...CID.3 .......
¿Está claro, no?
Po vale. Po bueno. Po ahora vamos a ver como buscar en un árbol.Hay 3 formas
de buscar:
A) IZQDA-RAIZ-DERECHA
B) RAIZ-IZQDA-DERECHA
C) IZQDA-DERECHA-RAIZ
Esto no es tan fácil como parece y de hecho es muy difícil de explicar. Os
pondré un ejemplo de árbol:
a El árbol se recorre así en cada caso:
/ \
b e A) cbdafeg
/\ /\ B) abcdefg
c d f g C) cdbfgea
Si no lo entendéis no calentaros demasiado la cabeza. Es igual en los tres
casos. Podéis inventaros otras formas de recorrerlo según se adapte a las
necesidades del programa. En cualquier caso, las tres anteriores son las
mejores.
En cada nodo del árbol, hay que guardar varios campos:
- Información: Es decir, el nombre de la ciudad o provincia en el caso
del juego, el nombre del directorio o fichero ...
- Un puntero hacia el nodo derecho
- Otro hacia el nodo izquierdo
Si el árbol tuviera más de dos ramas por nodo, habría que guardar tantos
campos como ramas.
Y como siempre, os incluyo un pequeño source que imprime un árbol por el
método A. Es simplemente como muestra para aquellos que les interese. ¡Ah!,
aquí también aparecen las funciones recursivas que he comentado en otro
artículo. Bueno, esto es todo. Os dejo con el programita ...
¡Hasta otra amigos!
/*Arboles binarios*/
/*Warlord Noviembre 1992*/
#include <malloc.h>
#include <stdio.h>
struct arb {
char info;
struct arb *izq;
struct arb *der;
}
sbstruct arb *raiz; /* primer nodo en el árbol*/
void imprime_arbol();
main() /*programa que imprime el arbol*/
{
char s[80];
struct arb *arbol();
raiz=NULL; /*inicializacion de la raiz*/
do {
printf("introduzca una letra; ");
gets(s);
if(!raiz) raiz=arbol(raiz,raiz,*s);
else arbol (raiz,raiz,*s);
} while (*s);
imprime_arbol(raiz,0);
}
struct arb *arbol(raiz,r,info)
struct arb *raiz;
struct arb *r;
char info;
{
if(!r) {
r=(struct arb *) malloc(sizeof(struct arb));
if(!r) {
printf("no hay memoria\n");
exit(0);
}
r->izq=NULL;
r->der=NULL;
r->info=info;
if(!raiz) return r; /*primera entrada*/
if(info<raiz->info) raiz->izq=r;
else raiz->der=r;
return r;
}
if(info<r->info) arbol(r,r->izq,info);
else
if(info>r->info) arbol(r,r->der,info);
}
void imprime_arbol(r,l)
struct arb *r;
int l;
{
int i;
if(!r) return;
imprime_arbol(r->izq,l+1);
for(i=0;i<l;++i) printf(" ");
printf("%c \n",r->info);
imprime_arbol(r->der,l+1);
}
|
