Programación del Sinclair QL (XXIV): Arboles. Estructura de los nodos en Super Basic

 

Índice de entradas sobre programación del Sinclair QL

---

Hemos visto el tema de las variables y el de los punteros, ahora vamos a hacer algo en Super Basic, pero ya que no es un lenguaje que soporte punteros ni se pueden usar variables compuestas de tipo registro, es un poco más complicado su manejo. Para manejar memoria hay que usar llamadas al Sistema Operativo para reservar memoria y código máquina para manejar los registros y punteros, o en el Toolkit II hay algunas funciones que nos lo facilitan. Como esto se sale de estas entradas que son de programación en SuperBasic, con la idea de que se pueda portar a otros Basic, voy a hacer otra cosas diferente para manejar árboles binarios, aunque no descarto luego hacer algo usando código máquina y llamadas al sistema.

Simularé la memoria usando una cadena de caracteres, usando el hecho de que una cadena tiene n caracteres, y podemos acceder a cualquiera de ellos individualmente, y cada carácter tiene un valor de 8 bits, lo que es muy similar a como se maneja una memoria. Desarrollaré funciones para reservar "memoria" dentro de la cadena, guardar datos en ella, leer cualquier dato usando un puntero a su dirección base, etc.

Nodos

Para crear los nodos del árbol, en entradas anteriores usé varios vectores de enteros, ya que los valores que manejamos lo eran. Ahora usaremos valores de tipo cadena de longitud variable, por lo que ya no nos sirve usar un vector, desperdiciamos demasiada memoria definiendo cadenas de longitud fija que pueden estar casi vacías. En su lugar en C se usaría un registro, que es una variable que se subdivide en varias, comportándose como un todo o como cada variable individual. Veamos como lo definiríamos en C:

struct nombre_registro    //El nombre que deseamos darle
{
     tipodato campo_1;    //Se define como cualquier variable, tipo y nombre
     tipodato campo_2;
     ....
     tipodato campo_N;    //Podemos usar todas las variables necesarias       
};


En el programa usaremos el nombre como el tipo de variable:

nombre_registro Variable_Registro;     //El nombre que deseamos darle a la variable

Y luego llamamos a los valores añadiendo un punto al nombre:

Variable_Registro.campo_n = ....
if (Variable_Registro.campo_n == true) {....


En los árboles binarios, necesitamos estos datos dentro para montar el registro:

• Nodo_Izquierdo: Puntero al sub-nodo izquierdo de este nodo.
• Nodo_Derecho: Puntero al sub-nodo derecho de este nodo.
• Nodo_Padre: Puntero al nodo padre de este nodo.Este dato no es estrictamente necesario, pero simplifica el montaje del árbol.
  
• Contenido del nodo: En nuestro caso es una cadena de caracteres, pero puede ser cualquier tipo, como un entero o un vector, o incluso otra estructura de tipo registro.
• Longitud del contenido: Al ser una cadena de longitud variable, necesitamos sabes su longitud para reservar solo la memoria necesaria.
  

Funciones para montar registros

Para montar un registro usaré una cadena de caracteres dividida en partes, los punteros serán valores numéricos entre 0 y 99, mientras que el contenido lo limitaremos a entre 0 y 99 caracteres. 

Para almacenar los números usaré cadenas de longitud fija, ajustadas a la izquierda con ceros por la derecha, así será sencillo ver su valor, realmente lo que se debe usar son bytes, con 1 byte podemos almacenar un número entero sin signo entre 0 y 255, con 2 bytes alcanzamos entre 0 y 65.535, esto pueden ser fácilmente dos caracteres, pero muchos no sería visibles ni nos informarían de los valores del puntero, por eso prefiero usar números almacenados en la cadena, aunque solo puedo almacenar entre 0 y 99 tengo la ventaja de que los puedo ver de forma sencilla, y este desarrollo intenta ser instructivo más que efectivo.

Nuestro nodos serán una cadena de caracteres con este formato <NN:NN:NN:NN:cadena> en donde:

• Inicio del nodo: Un carácter "<"
  
• Puntero al nodo padre: Dos caracteres numéricos. No es necesario pero simplifica la navegación por el árbol.
• Separador: Un carácter ":"
  
• Puntero al nodo hijo izquierdo: Dos caracteres numéricos.
• Separador: Un carácter ":"
  
• Puntero al nodo hijo derecho: Dos caracteres numéricos.
• Separador: Un carácter ":"
  
• Longitud del contenido: Dos caracteres numéricos.
• Separador: Un carácter ":"
  
• Contenido: Una cadena de entre 0 y 99 caracteres
• Fin del registro: Un carácter ">"

Los caracteres de inicio y fin no son necesarios, así como los separadores tampoco lo son, pero los usaré para poder ver los nodos de manera sencilla, y rellenaré la "memoria" con asteriscos, de forma que se vean los huecos libres, y cuando queramos ver la "memoria" lo podemos hacer simplemente imprimiendo la cadena, y veremos un texto de la forma:

<00:01:23:04:HOLA>******************<19:40:00:05;ADIOS><04:25_09:00:>********....

Así creo que es mas sencillo presentar los valores de forma que se vean correctamente, sin necesidad de grandes procesos.

Empecemos por las funciones que montan los nodos, para lo que defino funciones y procedimientos para manejarlas:

• inicializa: Este procedimiento inicializa las variables que usaremos, en donde:
• mLon: Longitud de las cadenas para guardar los punteros
• mNodos: Máximo número de nodos que manejamos
• nIni, nSep, nFin: inicio, separador y final para montar el nodo
• pPadre, pIzq, pDer, pLon, pVal: Orden de los campos para el nodo
  
• n2c$(n,l): Esta función retorna una cadena cuyo contenido es un valor numérico (n), ajustada a una longitud máxima (l) y rellena con ceros por la izquierda. Si le pasamos por ejemplo (17,3) nos retorna "017"

• MontarNodo$(p,i,d,c$): Función que retorna un nodo montado con los valores para el padre (p), hijo izquierdao (i), hijo derecho (d) y una cadena de caracteres (c$), si le pasamos por ejemplo (2,12,3,"Hola") nos retorna "<02:12:03:04:Hola>"

• NuevoNodo$(p,c$): Función que retorna un nuevo nodo sin hijos, con los valores para el padre (p) y una cadena de caracteres (c$), si le pasamos por ejemplo (2,"Hola") nos retorna "<02:00:00:04:Hola>"
• Posicion(pos): Retorna un número que indica donde comienza en la cadena que representa el nodo uno de los valores del nodo (pos con valores para 0=padre, 1=izquierdo, 2=derecho, 3=longitud del contenido, 4=valor del contenido), si le pasamos por ejemplo (pIzq) nos retorna 5
• NuevoHijo$(nodo$, pos, valor): Retorna una cadena que representa un nodo (nodo$), en la que cambia el puntero para uno de los hijos (pos donde 1=izquierdo o 2=derecho), con su nuevo valor de puntero (valor), si le pasamos por ejemplo ("<02:00:00:04:Hola>", pIzq,2) nos retorna "<02:02:00:04:Hola>"
• NuevoValor$(nodo$, NuevoValor$): Retorna una cadena que representa un nodo (nodo$), en la que cambia el valor del contenido (NuevoValor$), si le pasamos por ejemplo ("<02:02:00:04:Hola>", "Adios") nos retorna "<02:02:00:05:Adios>"

5000 REMark *************************************************************
5010 REMark * Librería.: Arbol Binario                                  *
5020 REMark * Programa.: Nodos                                          *
5030 REMark * Contenido: Rutinas de manejo de los nodos                 *
5040 REMark * Autor....: javu61, octubre 2024                           *
5050 REMark *************************************************************
5060 :
5070 REMark --- Inicializar el sistema
5080 :
5090 DEFine PROCedure inicializa
5100   mLon=2
5110   mNodos = 10^mLon - 1
5120   nIni$="<" : nSep$=":" : nFin$=">"
5130   pPadre=0 : pIzq=1 : pDer = 2 : pLon=3 : pVal=4
5140 END DEFine inicializa
5150 :
5160 REMark --- Numero en cadena ajustado a longitud
5170 :
5180 DEFine FuNction n2c$(n,l)
5190   LOCal c$
5200   c$=n
5210   REPeat bucle_n2c
5220     IF LEN(c$)>=l THEN EXIT bucle_n2c
5230     c$ = "0" & c$
5240   END REPeat bucle_n2c
5250   c$= c$(1 TO l)
5260   RETurn c$
5270 END DEFine n2c$
5280 :
5290 REMark --- Montar un nodo
5300 :
5310 DEFine FuNction MontarNodo$(p,i,d,c$)
5320   LOCal n$
5330   n$ = nIni$
5340   n$ = n$ & n2c$(p,mLon) & nSep$
5350   n$ = n$ & n2c$(i,mLon) & nSep$
5360   n$ = n$ & n2c$(d,mLon) & nSep$
5370   n$ = n$ & n2c$(LEN(c$),mLon) & nSep$ & c$
5380   n$ = n$ & nFin$
5390   RETurn n$
5400 END DEFine MontarNodo
5410 :
5420 REMark --- Montar un nodo nuevo sin hijos
5430 :
5440 DEFine FuNction NuevoNodo$(p,c$)
5450   RETurn MontarNodo$(p, 0, 0, c$)
5460 END DEFine NuevoNodo
5470 :
5480 REMark --- Retorna la posición de un elemento en el nodo
5490 :
5500 DEFine FuNction Posicion(pos)
5510   RETurn LEN(nIni$) + (pos * mLon) + (pos * LEN(nSep$)) + 1
5520 END DEFine Posicion
5530 :
5540 REMark --- Añadir un hijo a un nodo
5550 :
5560 DEFine FuNction NuevoHijo$(nodo$, pos, valor)
5570   LOCal p
5580   p = Posicion(pos)
5590   nodo$(p TO p+mLon-1)= n2c$(valor, mLon)
5600   RETurn nodo$
5610 END DEFine NuevoHijo$
5620 :
5630 REMark --- Cambiar el valor de un nodo
5640 :
5650 DEFine FuNction NuevoValor$(nodo$, NuevoValor$)
5660   LOCal p1,p2
5670   p1 = Posicion(pLon)
5680   p2 = Posicion(pVal)
5690   nodo$ = nodo$(1 TO p1-1)
5700   nodo$ = nodo$& n2c$(LEN(NuevoValor$), mLon) & nSep$
5710   nodo$ = nodo$ & NuevoValor$ & nFin$
5720   RETurn nodo$
5730 END DEFine NuevoValor$

 

En la siguiente entrada añadiré un programa para probar que estas funciones trabajen correctamente, y si queréis descargar este fichero lo tenéis aquí.