Tema 13: Variables dinámicas.

En Pascal estándar, tal y como hemos visto hasta ahora, tenemos una serie de variables que declaramos al principio del programa o de cada módulo (función o procedimiento, unidad, etc). Estas variables, que reciben el nombre de estáticas, tienen un tamaño asignado desde el momento en que se crea el programa.

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).

Vimos una introducción a los punteros y comentamos cómo se manejarían combinados con arrays. Antes de pasar a estructuras más complejas, vamos a hacer un ejemplo práctico (que realmente funcione).

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:         }
{    - Free Pascal 2.2.0w  }
{    - 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 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 Primera22 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.

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;

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

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 }

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 }

dato1^.siguiente := dato2;

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 }

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

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

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;

{--------------------------}
{  Ejemplo en Pascal:      }
{                          }
{    Ejemplo de listas     }
{    dinámicas enlazadas   }
{    LISTAS.PAS            }
{                          }
{  Este fuente procede de  }
{  CUPAS, curso de Pascal  }
{  por Nacho Cabanes       }
{                          }
{  Comprobado con:         }
{    - Free Pascal 2.2.0w  }
{    - 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