Tema 13: Variables dinámicas.

Esto es cómodo para detectar errores y rápido si vamos a manejar estruturas de datos que no cambien, pero resulta poco eficiente si tenemos estructuras cuyo tamaño no sea siempre el mismo.

Es el caso de una agenda: tenemos una serie de fichas, e iremos añadiendo más. Si reservamos espacio para 10, no podremos llegar a añadir la número 11, estamos limitando el máximo. En este caso, la solución que vimos fue la de trabajar siempre en el disco. No tenemos límite en cuanto a número de fichas, pero es muchísimo más lento.

Lo ideal sería aprovechar mejor la memoria que tenemos en el ordenador, para guardar en ella todas las fichas o al menos todas aquellas que quepan en memoria.

Una solución "típica" es sobredimensionar: preparar una agenda contando con 1000 fichas, aunque supongamos que no vamos a pasar de 200. Esto tiene varios inconvenientes: se desperdicia memoria, obliga a concer bien los datos con los que vamos a trabajar, sigue pudiendo verse sobrepasado, y además en Turbo Pascal tenemos muy poca memoria disponible para variables estáticas: 64K (un segmento, limitaciones heredadas del manejo de memoria en el DOS en modo real).

Por ejemplo, si en nuestra agenda guardamos lo siguientes datos de cada persona: nombre (40 letras), dirección (2 líneas de 50 letras), teléfono (10 letras), comentarios (70 letras), que tampoco es demasiada información, tenemos que cada ficha ocupa 235 bytes, luego podemos almacenar menos de 280 fichas en memoria, incluso suponiendo que las demás variables que empleemos ocupen muy poco espacio.

Todas estas limitaciones se solucionan con el uso de variables dinámicas, para las cuales se reserva espacio en el momento de ejecución del programa, sólo en la cantidad necesaria, se pueden añadir elementos después, y se puede aprovechar toda la memoria convencional (primeros 640K) de nuestro equipo.

Si además nuestro compilador genera programas en modo protegido del DOS, podremos aprovechar toda la memoria real de nuestro ordenador (4 Mb, 8 Mb, etc). Si crea programas para sistemas operativos que utilicen memoria virtual (como OS/2 o Windows, que destinan parte del disco duro para intercambiar con zonas de la memoria principal, de modo que aparentemente tenemos más memoria disponible), podremos utilizar también esa memoria de forma transparente para nosotros.

Así que se acabó la limitación de 64K. Ahora podremos tener, por ejemplo, 30 Mb de datos en nuestro programa y con un acceso muchísimo más rápido que si teníamos las fichas en disco, como hicimos antes.

Ahora "sólo" queda ver cómo utilizar estas variables dinámicas. Esto lo vamos a ver en 3 apartados. El primero (éste) será la introducción y veremos cómo utilizar arrays con elementos que ocupen más de 64K. El segundo, manejaremos las "listas enlazadas". El tercero nos centraremos en los "árboles binarios" y comentaremos cosas sobre otras estructuras.

Vamos allá...

La idea de variable dinámica está muy relacionada con el concepto de puntero (o apuntador, en inglés "pointer"). Un puntero es una variable que "apunta" a una determinada posición de memoria, en la que se encuentran los datos que nos interesan.

Como un puntero almacena una dirección de memoria, sólo gastará 4 bytes de esos 64K que teníamos para datos estáticos. El resto de la memoria (lo que realmente ocupan los datos) se asigna en el momento en el que se ejcuta el programa y se toma del resto de los 640K. Así, si nos quedan 500K libres, podríamos guardar cerca de 2000 fichas en memoria, en vez de las 280 de antes. De los 64K del segmento de datos sólo estaríamos ocupando cerca de 8K (2000 fichas x 4 bytes).

Veamoslo con un ejemplo (bastante inútil, "púramente académico" X-D ) que después comentaré un poco.

{--------------------------}
{  Ejemplo en Pascal:      }
{                          }
{    Primer ejemplo de     }
{    variables dinámicas   }
{    DINAM1.PAS            }
{                          }
{  Este fuente procede de  }
{  CUPAS, curso de Pascal  }
{  por Nacho Cabanes       }
{                          }
{  Comprobado con:         }
{    - Turbo Pascal 7.0    }
{--------------------------}

program Dinamicas;

type
  pFicha = ^Ficha;                     (* Puntero a la ficha *)

  Ficha = record                       (* Datos almacenados *)
    nombre: string[40];
    edad: byte
    end;

var
  fichero: file of ficha;              (* El fichero, claro *)
  datoLeido: ficha;                    (* Una ficha que se lee *)
  indice: array [1..1000] of pFicha;   (* Punteros a 1000 fichas *)
  contador: integer;                   (* Nº de fichas que se lee *)

begin
  assign( fichero, 'Datos.Dat' );      (* Asigna el fichero *)
  reset( fichero );                    (* Lo abre *)
  for contador := 1 to 1000 do         (* Va a leer 1000 fichas *)
    begin
    read( fichero, datoleido );        (* Lee cada una de ellas *)
    new( indice[contador] );           (* Le reserva espacio *)
    indice[contador]^ := datoLeido;    (* Y lo guarda en memoria *)
    end;
  close( fichero );                    (* Cierra el fichero *)
  writeln('El nombre de la ficha 500 es: ');
  writeln(indice[500]^.nombre);
  for contador := 1 to 1000 do         (* Liberamos memoria usada *)
    dispose( indice[contador] );
end.

El acento circunflejo (^) quiere decir "que apunta a" o "apuntado por". Así,

pFicha = ^Ficha;

indica que pFicha va a "apuntar a" datos del tipo Ficha, y

indice[500]^.nombre

será el campo nombre del dato al que apunta la dirección 500 del índice. El manejo es muy parecido al de un array que contenga records, como ya habíamos visto, con la diferencia de el carácter ^, que indica que se trata de punteros.

Antes de asignar un valor a una variable dinámica, hemos de reservarle espacio con "new", porque si no estaríamos escribiendo en una posición de memoria que el compilador no nos ha asegurado que esté vacía, y eso puede hacer que "machaquemos" otros datos, o parte del propio programa, o del sistema operativo... esto es muy peligroso, y puede provocar desde simples errores muy difíciles de localizar hasta un "cuelgue" en el ordenador o cosas más peligrosas...

Cuando terminamos de utilizar una variable dinámica, debemos liberar la memoria que habíamos reservado. Para ello empleamos la orden "dispose", que tiene una sintaxis igual que la de new:

new( variable ); { Reserva espacio }
dispose( variable ); { Libera el espacio reservado }

Bueno, ya está bien por ahora. Hemos visto una forma de tener arrays de más de 64K de tamaño, pero seguimos con la limitación en el número de fichas. En el próximo apartado veremos cómo evitar también esto...

Experimentad, experimentad... }

Tema 13.2: Variables dinámicas (2).

Tomando la base que vimos, vamos a hacer un lector. Algo parecido al README.COM que incluyen Borland y otras casas en muchos de sus programas.

Es un programa al que le decimos el nombre de un fichero de texto, lo lee y lo va mostrando por pantalla. Podremos desplazarnos hacia arriba y hacia abajo, de línea en línea o de pantalla en pantalla. Esta vez, en vez de leer un registro "record", leeremos "strings", y por comodidad los limitaremos a la anchura de la pantalla, 80 caracteres. Tendremos una capacidad, por ejemplo, de 2000 líneas, de modo que gastaremos como mucho 80*2000 = 160 K aprox.

Hay cosas que se podrían hacer mejor, pero me he centrado en procurar que sea lo más legible posible. Espero haberlo conseguido...

Eso sí: un comentario obligado: eso que aparece en el fuente de #27 es lo mismo que escribir "chr(27)", es decir, corresponde al carácter cuyo código ASCII es el 27.

Vamos allá...

{--------------------------}
{  Ejemplo en Pascal:      }
{                          }
{    Lector de ficheros    }
{    de texto              }
{    LECTOR.PAS            }
{                          }
{  Este fuente procede de  }
{  CUPAS, curso de Pascal  }
{  por Nacho Cabanes       }
{                          }
{  Comprobado con:         }
{    - Turbo Pascal 7.0    }
{    - Tmt Pascal Lt 1.20  }
{--------------------------}

program Lector;             { Lee ficheros de texto }

uses                                   { Unidades externas: }
   crt;                                { Pantalla de texto y teclado }

const
   MaxLineas = 2000;                   { Para modificarlo facilmente }

   kbEsc = #27;                        { Código ASCII de la tecla ESC }

   kbFuncion = #0;                     { Las teclas de función devuelven
                                         0 + otro código }
   kbArr = #72;                        { Código de Flecha Arriba }
   kbPgArr = #73;                      { Página Arriba }
   kbAbj = #80;                        { Flecha Abajo }
   kbPgAbj = #81;                      { Página Abajo }


type
  LineaTxt = string [80];              { Una línea de texto }
  PLineaTxt = ^LineaTxt;               { Puntero a lína de texto }
  lineas = array[1..maxLineas]         { Nuestro array de líneas }
      of PLineaTxt;

var
  nomFich: string;                     { El nombre del fichero }
  fichero: text;                       { El fichero en sí }
  datos: lineas;                       { Los datos, claro }
  lineaActual: string;                 { Cada línea que lee del fichero }
  TotLineas: word;                     { El número total de líneas }
  Primera: word;                       { La primera línea en pantalla }


Procedure Inicio;                      { Abre el fichero }
begin
  textbackground(black);               { Colores de comienzo: fondo negro }
  textcolor(lightgray);                {   y texto gris }
  clrscr;                              { Borramos la pantalla }
  writeln('Lector de ficheros de texto.');
  writeln;
  write('Introduzca el nombre del fichero: ');
  readln(nomFich);
end;


Procedure Pantalla;                    { Pantalla del lector }
begin
  textbackground(red);                 { Bordes de la pantalla }
  textcolor(yellow);                   { Amarillo sobre rojo }
  clrscr;                              { ... }
  gotoxy(2,1);
  write('Lector de ficheros de texto. Nacho Cabanes, 95.'
   +'           Pulse ESC para salir');
  gotoxy(2,25);
  write('Use las flechas y AvPag, RePag para moverse.');
  window(1,2,80,24);                   { Define una ventana interior }
  textbackground(black);               { Con distintos colores }
  textcolor(white);
  clrscr;
end;


Procedure EscribeAbajo(mensaje: string);    { Escribe en la línea inferior }
begin
  window(1,1,80,25);                   { Restaura la ventana }
  textbackground(red);                 { Colores de los bordes: }
  textcolor(yellow);                   { Amarillo sobre rojo }
  gotoxy(60,25);                       { Se sitúa }
  write(mensaje);                      { y escribe }
  window(1,2,80,24);                   { Redefine la ventana interior }
  textbackground(black);               { y cambia los colores }
  textcolor(white);
end;


procedure salir;                       { Antes de abandonar el programa }
var i: word;
begin
  for i := 1 to TotLineas              { Para cada línea leída, }
    do dispose(datos[i]);              {  libera la memoria ocupada }
  window(1,1,80,25);                   { Restablece la ventana de texto, }
  textbackground(black);               { el color de fondo, }
  textcolor(white);                    { el de primer plano, }
  clrscr;                              { borra la pantalla }
  writeln('Hasta otra...');            { y se despide }
end;


Procedure Pausa;                       { Espera a que se pulse una tecla }
var tecla:char;
begin
  tecla:=readkey;
end;


Function strs(valor:word):string;      { Convierte word a string }
var cadena: string;
begin
  str(valor,cadena);
  strs := cadena;
end;

function min(a,b: word): word;         { Halla el mínimo de dos números }
begin
  if a<b then min := a else min := b;
end;


procedure Lee;
begin;
  clrscr;
  TotLineas := 0;                      { Inicializa variables }
  Primera := 0;
  while (not eof(fichero))             { Mientras quede fichero }
      and (TotLineas < MaxLineas) do   { y espacio en el array }
    begin
    readln( fichero, LineaActual );      { Lee una línea }
    TotLineas := TotLineas + 1 ;         { Aumenta el contador }
    new(datos[TotLineas]);               { Reserva memoria }
    datos[TotLineas]^ := LineaActual;    { y guarda la línea }
    end;
  if TotLineas > 0                     { Si realmente se han leido líneas }
    then Primera := 1;                 {   empezaremos en la primera }
  close(fichero);                      { Al final, cierra el fichero }
end;



procedure Muestra;                     { Muestra el fichero en pantalla }
var
  i: word;                             { Para bucles }
  tecla: char;                         { La tecla que se pulsa }
begin;
  repeat
    for i := Primera to Primera+22 do
      begin
      gotoxy(1, i+1-Primera );         { A partir de la primera línea }
      if datos[i] <> nil then          { Si existe dato correspondiente, }
        write(datos[i]^);              {   lo escribe }
      clreol;                          { Y borra hasta fin de línea }
      end;
    EscribeAbajo('Líneas:'+strs(Primera)+'-'+
      strs(Primera+22)+'/'+strs(TotLineas)+' ');
    tecla := readkey ;
    if tecla = kbFuncion then begin    { Si es tecla de función }
      tecla := readkey;                { Mira el segundo código }
      case tecla of
        kbArr:                         { Flecha arriba }
          if Primera>1 then Primera := Primera -1;
        kbAbj:                         { Flecha abajo }
          if Primera<TotLineas-22 then Primera := Primera + 1;
        kbPgArr:                       { Página arriba }
          if Primera>22 then Primera := Primera - 22
            else Primera := 1;
        kbPgAbj:                       { Página Abajo }
          if Primera< (TotLineas-22) then
            Primera := Primera + min(22, TotLineas-23)
            else Primera := TotLineas-22;
        end;
      end;
  until tecla = kbEsc;
end;

begin
  Inicio;                              { Pantalla inicial }
  assign(fichero, nomFich);            { Asigna el fichero }
  {$I-}                                { desactiva errores de E/S }
  reset(fichero);                      { e intenta abrirlo }
  {$I+}                                { Vuelve a activar errores }
  if IOresult = 0 then                { Si no ha habido error }
    begin
    Pantalla;                            { Dibuja la pantalla }
    Lee;                                 { Lee el fichero }
    Muestra;                             { Y lo muestra }
    end
  else                                 { Si hubo error }
    begin
    writeln(' ¡ No se ha podido abrir el fichero ! ');   { Avisa }
    pausa;
    end;
  salir                                { En cualq. caso, sale al final }
end.

Pues eso es todo por hoy...

(Si aparece alguna cosa "rara", como la palabra NIL, no te preocupes: en el próximo apartado está explicada).

Tema 13.3: Variables dinámicas (3).

Después vimos con más detalle como podíamos hacer arrays de más de 64K. Aprovechábamos mejor la memoria y a la vez seguíamos teniendo acceso directo a cada dato. Como inconveniente: no podíamos añadir más datos que los que hubiéramos previsto al principio (2000 líneas en el caso del lector de ficheros que vimos como ejemplo).

Pues ahora vamos a ver dos tipos de estructuras totalmente dinámicas (frente a los arrays, que eran estáticos). En esta lección serán las listas, y en la próxima trataremos los árboles binarios. Hay otras muchas estructuras, pero no son difíciles de desarrollar si se entienden bien estas dos.

Ahora "el truco" consistirá en que dentro de cada dato almacenaremos todo lo que nos interesa, pero también una referencia que nos dirá dónde tenemos que ir a buscar el siguiente.

Sería algo así como:

(Posición: 1023).
Nombre : 'Nacho Cabanes'
DireccionFido : '2:346/3.30'
SiguienteDato : 1430

Este dato está almacenado en la posición de memoria número 1023. En esa posición guardamos el nombre y la dirección (o lo que nos interese) de esta persona, pero también una información extra: la siguiente ficha se encuentra en la posición 1430.

Así, es muy cómodo recorrer la lista de forma secuencial, porque en todo momento sabemos dónde está almacenado el siguiente dato. Cuando lleguemos a uno para el que no esté definido cual es el siguiente, quiere decir que se ha acabado la lista.

Hemos perdido la ventaja del acceso directo: ya no podemos saltar directamente a la ficha número 500. Pero, por contra, podemos tener tantas fichas como la memoria nos permita.

Para añadir un ficha, no tendríamos más que reservar la memoria para ella, y el Turbo Pascal nos diría "le he encontrado sitio en la posición 4079". Así que nosotros iríamos a la última ficha y le diríamos "tu siguiente dato va a estar en la posición 4079".

Esa es la idea "intuitiva". Espero que a nadie le resulte complicado. Así que vamos a empezar a concretar cosas en forma de programa en Pascal.

Primero cómo sería ahora cada una de nuestras fichas:

type
pFicha = ^Ficha; { Puntero a la ficha }

Ficha = record { Estos son los datos que guardamos: }
nombre: string[30]; { Nombre, hasta 30 letras }
direccion: string[50]; { Direccion, hasta 50 }
edad: byte; { Edad, un numero < 255 }
siguiente: pFicha; { Y dirección de la siguiente }
end;

La nomenclatura ^Ficha ya la habíamos visto. Se refiere a que eso es un "puntero al tipo Ficha". Es decir, la variable "pFicha" va a tener como valor una dirección de memoria, en la que se encuentra un dato del tipo Ficha.

La diferencia está en el campo "siguiente" de nuestro registro, que es el que indica donde se encuentra la ficha que va después de la actual.

Un puntero que "no apunta a ningún sitio" tiene el valor NIL, que nos servirá después para comprobar si se trata del final de la lista: todas las fichas "apuntarán" a la siguiente, menos la última, que "no tiene siguiente"

Entonces la primera ficha la definiríamos con

var dato1: pFicha; { Va a ser un puntero a ficha }

y la crearíamos con

new (dato1); { Reservamos memoria }
dato1^.nombre := 'Pepe'; { Guardamos el nombre, }
dato1^.direccion := 'Su casa'; { la dirección }
dato1^.edad := 102; { la edad :-o }
dato1^.siguiente := nil; { y no hay ninguna más }

Ahora podríamos añadir una ficha detrás de ella. Primero guardamos espacio para la nueva ficha, como antes:

var dato2: pFicha; { Va a ser otro puntero a ficha }

new (dato2); { Reservamos memoria }
dato2^.nombre := 'Juan'; { Guardamos el nombre, }
dato2^.direccion := 'No lo sé'; { la dirección }
dato2^.edad := 35; { la edad }
dato2^.siguiente := nil; { y no hay ninguna detrás }

y ahora enlazamos la anterior con ella:

dato1^.siguiente := dato2;

Si quisieramos introducir los datos ordenados alfabéticamente, basta con ir comparando cada nuevo dato con los de la lista, e insertarlo donde corresponda. Por ejemplo, para insertar un nuevo dato entre los dos anteriores, haríamos:

var dato3: pFicha; { Va a ser otro puntero a ficha }
new (dato3);
dato3^.nombre := 'Carlos';
dato3^.direccion := 'Por ahí';
dato3^.edad := 14;
dato3^.siguiente := dato2; { enlazamos con la siguiente }
dato1^.siguiente := dato3; { y con la anterior }

La estructura que hemos obtenido es la siguiente

Dato1 - Dato3 - Dato2 - nil

o gráficamente:

+------+ +------+ +------+
¦Dato1 ¦ +->--¦Dato3 ¦ +->--¦Dato2 ¦
+------¦ ¦ +------¦ ¦ +------¦
+--+ +-+ +------------+
---------
--- nil

Es decir: cada ficha está enlazada con la siguiente, salvo la última, que no está enlazada con ninguna (apunta a NIL).

Si ahora quisiéramos borrar Dato3, tendríamos que seguir dos pasos:

1.- Enlazar Dato1 con Dato2, para no perder información.
2.- Liberar la memoria ocupada por Dato3.

Esto, escrito en "paskalero" sería:

dato1^.siguiente := dato2; { Enlaza Dato1 y Dato2 }
dispose(dato3); { Libera lo que ocupó Dato3 }

Hemos empleado tres variables para guardar tres datos. Si tenemos 20 datos, ¿necesitaremos 20 variables? ¿Y 3000 variables para 3000 datos?

Sería tremendamente ineficiente, y no tendría mucho sentido. Es de suponer que no sea así. En la práctica, basta con dos variables, que nos indicarán el principio de la lista y la posición actual, o incluso sólo una para el principio de la lista.

Por ejemplo, un procedimiento que muestre en pantalla toda la lista se podría hacer de forma recursiva así:

procedure MuestraLista ( inicial: pFicha );
begin
if inicial <> nil then { Si realmente hay lista }
begin
writeln('Nombre: ', inicial^.nombre);
writeln('Dirección: ', inicial^.direccion);
writeln('Edad: ', inicial^.edad);
MuestraLista ( inicial^.siguiente ); { Y mira el siguiente }
end;
end;

Lo llamaríamos con "MuestraLista(Dato1)", y a partir de ahí el propio procedimiento se encarga de ir mirando y mostrando los siguientes elementos hasta llegar a NIL, que indica el final.

Aquí va un programilla de ejemplo, que ordena los elementos que va insertando... y poco más } :

{--------------------------}
{  Ejemplo en Pascal:      }
{                          }
{    Ejemplo de listas     }
{    dinámicas enlazadas   }
{    LISTAS.PAS            }
{                          }
{  Este fuente procede de  }
{  CUPAS, curso de Pascal  }
{  por Nacho Cabanes       }
{                          }
{  Comprobado con:         }
{    - Turbo Pascal 7.0    }
{    - Tmt Pascal Lt 1.20  }
{--------------------------}

program EjemploDeListas;

type
  puntero = ^TipoDatos;
  TipoDatos = record
    numero: integer;
    sig:    puntero
  end;


function CrearLista(valor: integer): puntero;  {Crea la lista, claro}
var
  r: puntero;                 { Variable auxiliar }
begin
  new(r);                     { Reserva memoria }
  r^.numero := valor;         { Guarda el valor }
  r^.sig := nil;              { No hay siguiente }
  CrearLista := r             { Crea el puntero }
end;


procedure MuestraLista ( lista: puntero );
begin
  if lista <> nil then               { Si realmente hay lista }
    begin
    writeln(lista^.numero);          { Escribe el valor }
    MuestraLista (lista^.sig )       { Y mira el siguiente }
    end;
end;


procedure InsertaLista( var lista: puntero; valor: integer);
var
  r: puntero;                         { Variable auxiliar }
begin
  if lista <> nil then                { Si hay lista }
    if lista^.numero<valor            {   y todavía no es su sitio }
      then                            {   hace una llamada recursiva: }
      InsertaLista(lista^.sig,valor)  {   mira la siguiente posición }
    else                              { Caso contrario: si hay lista }
      begin                           {   pero hay que insertar ya: }
      new(r);                         {   Reserva espacio, }
      r^.numero := valor;             {   guarda el dato }
      r^.sig := lista;                {   pone la lista a continuac. }
      lista := r                      {   Y hace que comience en }
      end                             {     el nuevo dato: r }
  else                                { Si no hay lista }
    begin                             {   deberá crearla }
    new(r);                           {   reserva espacio }
    r^.numero := valor;               {   guarda el dato }
    r^.sig := nil;                    {   no hay nada detrás y }
    lista := r                        {   hace que la lista comience }
    end                               {     en el dato: r }
end;


var
  l: puntero;             { Variables globales: la lista }

begin
  l := CrearLista(5);     { Crea una lista e introduce un 5 }
  InsertaLista(l, 3);     { Inserta un 3 }
  InsertaLista(l, 2);     { Inserta un 2 }
  InsertaLista(l, 6)