COLAS y ARBOLES
Edwinbeltr
estoy buscando el tema COLAS y ARBOLES en estructura de datos y
necesitaba que por favor me enviaran sugerencias de libros o links
donde pueda encontrar informacion acerca de este tema.
agradesco la informacion que me puedan brindar acerca de este tema
Edwinbeltr
Ronny Gómez
que está orientada hacia Vb pero puede servirte. Cualquier libro de
estructura de datos es bueno, ya que los conceptos de pilas y árboles
son muy sencillos.
Saludos y espero que te sirva,
Ronny
*-*-*-*-*-*-*-*-*-*-*-*
Existen medios para permitirte generar las estructuras de datos
que tú desees, que, a final de cuentas, es para lo que más se utilizan
los
punteros. Así, con los recursos de Visual Basic puedes generar listas
enlazadas, listas doblemente enlazadas, árboles, colas, etcétera.
El trabajo se basa en las clases integradas a Visual Basic. Te
ampliaré la
información:
Las estructuras de datos son un tema que siempre ha causado comezón a
más de
un programador que viene de lenguajes que no soportan apuntadores o
punteros. Para cualquiera que provenga de BASIC, COBOL, etcétera, las
estructuras son un tema bastante espinoso que pueden crear un buen
dolor de
cabeza. Pues bien, vamos a empezar por entender eso que parece tan
difícil y
que se llaman apuntadores o punteros.
Apuntadores
Para entender a los apuntadores, primero hay que entender a las
variables.
Una variable es un área de memoria que contiene datos y que está
representada por un nombre único. Para hacerlo más simple, imagina una
caja
donde metas lápices. Tal caja podría llamarse "Lapicero" y estará
destinada
a sólo contener lápices. Cuando se requiera de un lápiz, tan sólo te
diriges
al "Lapicero" y tomas uno de su interior. Si deseas guardar un lápiz,
irás
al "Lapicero" y lo colocarás allí. Una variable funciona de manera muy
similar. Cuando declaras una variable en realidad abres un espacio (o
caja)
en la memoria donde guardarás u obtendrás datos específicos. Tal área
de
memoria se identifica con un nombre específico en el programa, que es
el
mismo que le diste al declararla.
Ahora bien ¿qué es lo que ocurre cuando se necesitan múltiples
variables del
mismo tipo para almacenar información de manera organizada? Se pueden
crear
estructuras de datos. Las estructuras de datos serían pilas de cajas
que
contienen información de tipo similar. Sería como una de las grandes
pilas
de cajas en los supermercados. No obstante, el cerrarse a esta
definición
podría hacernos quedar lejos de lo que son las estructuras de datos
requeridas en la programación real.
Es decir, si lo comparamos con versiones anteriores de BASIC, la única
estructura viable era la matriz (o arreglo). No obstante, la
información no
siempre está apilada y menos aún se puede saber de antemano y en todos
los
casos cuántos elementos se necesitarían almacenar en la estructura de
datos.
Volvamos a la ilustración: imagina que compras una bodega donde se
almacenarían los productos que fabriques. Si la producción es muy
pequeña,
se desperdiciaría espacio en la bodega, si la producción es muy
grande,
podría faltar espacio para almacenarla. Esto, en la vida real, es un
problema un poco complejo de resolver, pero en la programación se
resuelve
mediante estructuras de datos dinámicas que soliciten la memoria
conforme
sea necesaria (ni más, ni menos).
Tal vez me podrías decir que Visual Basic cuenta con matrices que
pueden ser
redimensionables con ReDim. Yo te contestaría que esa sería una buena
opción
si no surgiera la necesidad de agregar elementos al principio de la
matriz y
no solamente al final (como sucede en este caso). Es decir, debería
tener la
suficiente versatilidad como para poder agregar o eliminar elementos
de
cualquier parte de la estructura (al inicio, al final o en zonas
intermedias) sin mayor problema.
Tal vez, nuevamente, me podrías decir que Visual Basic incluye algo
que se
llama Colecciones, y que con eso mi problema quedaría resuelto. Yo te
contestaría que son una solución excelente y muy eficiente para el
problema.
No obstante, aunque su estructura se basa en apuntadores a objetos, su
manera de manejarse podría dar más la idea de matrices y no de
apuntadores
como tales. Así que (pensarás), ya no queda mucho de dónde agarrarse
en
Visual Basic. Yo te contestaré que sí queda, y mucho.
Un apuntador, para definirlo como tal, es un tipo especial de variable
que
no contiene un valor, sino que más bien apunta (como su nombre lo
indica) a
algún lugar de la memoria donde el valor requerido se encuentra. Tal
valor
puede ser de cualquiera de los tipos de datos u objetos que soporte el
lenguaje en cuestión. Volvamos a la ilustración: supón que tienes una
persona encargada del almacén que lleva su administración. El
encargado debe
saber exactamente dónde se encuentra cada cosa y dónde acomodar
aquello de
reciente ingreso. Tú no deberás preocuparte del lugar donde se
coloquen u
obtengan las cosas, tan sólo las almacenas o las solicitas. El
apuntador
sería el almacenista que sabe dónde se ha colocado la información y de
dónde
obtenerla. Ahora bien, una vez que el concepto general de apuntador ha
sido
comprendido, veamos las estructuras de datos.
Estructuras de datos
Existen diversas estructuras de datos, pero hay cuatro básicas: Listas
enlazadas, Pilas, Colas y Árboles. Cada una de las estructuras está
formada
por elementos que se conocen como Nodos. Cada nodo tiene,
forzosamente, una
referencia a uno o más nodos que le permite organizarse en estructuras
(ve
la figura basic120a.tif). Cada uno de los nodos es de tipo similar a
todos
los demás en la estructura. A continuación veremos una rápida
explicación de
lo que son este tipo de estructuras.
Las listas enlazadas pueden ser de varios tipos: Listas con enlace
simple,
listas doblemente enlazadas y listas circulares. Las listas son el
medio más
utilizado de estructuras de datos en la programación con apuntadores y
ofrecen un medio muy versátil para almacenar información organizada.
Las Pilas: Son elementos que contienen un dato y un área que apunta al
siguiente nodo de la pila. Es lo más parecido que hay a las matrices
comunes.
Las colas: Es un conjunto de elementos al que pueden agregarse nodos
sólo
por un extremo y extraerlos sólo por el otro. De hecho su nombre se
debe a
su semejanza con las colas, formaciones o filas de la vida real: tú
llegas,
te formas y esperas a que los de enfrente sean atendidos hasta que te
toca a
tí; mientras, ya hubo otras personas que se formaron detrás tuyo.
Los árboles: Esta es una estructura que no es lineal. Los árboles
definen un
entorno jerárquico, donde los nodos pueden tener un padre e hijos (el
padre
sería el nodo del que se depende y los hijos serían los nodos que de
éste
dependen). Por lo general, los árboles son binarios, es decir, tienen
un
padre y dos posibles hijos. Estas estructuras son ricas y se aplican a
aquellos datos que requieren ser organizados de manera jerárquica.
Cualquier detractor de Visual Basic podría decir que es casi imposible
utilizar este tipo de estructuras de datos en el entorno. No obstante,
VB
tiene varios ases bajo la manga y, a continuación, explicaré a detalle
la
manera de utilizar tales estructuras sin problemas.
La generación de estructuras de datos complejas en Visual Basic
En realidad, déjame decirte que VB cuenta con apuntadores, aunque no
apuntan
a datos como tales, sino a objetos. Si has manejado Visual Basic
seguramente
has utilizado la palabra clave Set. Bien, pues esta palabra clave es
la que,
en sí, sirve para establecer un apuntador.
Veamos la estructura de Set:
Set var = [New] obj
Donde: Set es la palabra clave que le indica a Visual Basic que la
variable
(var) indicada inmediatamente después, apuntará al objeto (obj) que se
encuentra luego del signo de igual (=). Si se agrega la palabra clave
New,
entonces var apuntará a una nueva instancia del objeto (obj) indicado.
Con
esto, var sería capaz de reconocer todas las características y métodos
del
objeto al que apunta y, por medio de ella, se podrá acceder a ellos.
Esto
podría entenderse como lo siguiente: "Haz que por medio de 'var' me
pueda
comunicar con 'obj'". O también: "Haz que por medio de 'var' me pueda
comunicar con la nueva instancia de 'obj'".
En realidad, eso es lo que hacen los apuntadores, sólo que se
acostumbra
utilizarlos con tipos de datos estándar. Tú se preguntarás ¿y cómo,
entonces, se pueden crear las estructuras de datos complejas en Visual
Basic? Fácil: con clases. Las clases ofrecen una modalidad eficiente y
rápida para poder instaurar cualquier estructura que se necesite,
incluso
con creces.
Cada nodo de cualquier estructura antes citada podría no sólo contener
datos, sino que también podría contener cierta funcionalidad que
permitiese
aprovechar de mejor manera su existencia. El desempeño de un programa
que
utilice estructuras de datos de esta índole en Visual Basic es
bastante
bueno, e incluso adecuado para aplicaciones de misión crítica.
Ejemplo de una Lista doblemente enlazada
Aunque podríamos partir de cualquier estructura, una lista doblemente
enlazada servirá de buen ejemplo. Cada nodo de una estructura de este
tipo
debe tener una referencia al nodo anterior y al posterior para, con
ello,
hacer el doble enlace. La ventaja de una lista doblemente enlazada es
que se
puede explorar en cualquier dirección.
Ve la Figura basic120b.tif. En ella se ilustra la manera en que
luciría el
nodo. Este nodo tiene una referencia tanto al nodo anterior como al
siguiente. Además, tiene un dato (que podría ser toda una estructura,
un
objeto, una variable o lo que desees) que es el valor que allí se
almacena.
Al final del ejemplo, tendríamos una lista doblemente enlazada que
luciría
como la Figura basic120c.tif. Para este ejemplo se requiere de Visual
Basic
4 o superior.
El ejemplo consistirá de la generación de una lista de 10 números
aleatorios
que se asignarán a la lista doblemente enlazada. Primero hay que crear
el
nodo mediante una clase. Agrega una clase a su proyecto. Llámala
clsNodo y
teclea el siguiente código en el área General Declarations de la
clase:
Public NAnt As Object
Public NSig As Object
Public Valor As Integer
NAnt será la referencia al nodo anterior y NSig será la referencia al
siguiente nodo. Valor tendrá el número aleatorio del nodo. Ahora, en
el
formulario coloca una etiqueta y dos botones de comando. Guíate por la
Figura basic120c.tif. Deja los nombres predeterminados de los
controles.
Ahora teclea el código de la Figura basic120d.tif.
Va la explicación: Declaramos el apuntador a un nodo. El procedimiento
Command1_Click sirve para moverse al nodo anterior y Command2_Click
para
moverse al siguiente nodo. Ambos hacen su movimiento correspondiente y
muestran el contenido del nodo. El movimiento se hace al verificar si
las
referencias NAnt o NSig apuntan a algo, de ser cierto, se mueven a ese
nodo.
El código de Form_Load es el que genera los 10 nodos. En el bucle
For.Next
se agregan todos los nodos a la lista. A cada nodo se le establece un
valor
aleatorio y sus referencias. Al final del procedimiento, se ejecuta el
código del Command2. Con esto, aparecerá el formulario y podrás,
entonces,
hacer clic en los botones < y > para moverse por los nodos.
Este ejemplo es demasiado sencillo como para explotar todas las
ventajas de
utilizar una lista doblemente enlazada. Sin embargo, puedes ir a mi
página
Web (http://www.spin.com.mx/~adgarza) y obtener, del área de Archivos
y
utilerías, el programa ListEnla.zip que es un código mucho mejor
estructurado y que aprovecha mejor la Lista doblemente enlazada. Este
mismo
archivo lo incluyo en este mensaje. La base de estas estructuras es el
nodo,
al entenderlo se entiende el manejo de todas las demás estructuras.
El código de ListEnla.zip requiere de VB4 o superior y se encuentra
completamente documentado de manera que te sea fácil entender qué hace
cada
línea. Incluye tres procedimientos básicos: Inserta, Elimina y Cuenta.
Estos
podrían ser la raíz de tus aplicaciones que requiriesen listas
doblemente
enlazadas y la adaptación sería trivial. En conclusión: el uso de
estructuras de datos puede facilitarte muchas cosas.