Capítulo 6

.
Tipos de Datos definidos por el Programador

Los lenguajes de programación brindan la posibilidad al programador de definir sus propios tipos de datos.

En Pascal tenemos la sección type donde podemos definir nuevos tipos. Un ejemplo de esto es el siguiente programa en el que se definen los tipos de datos: Entero y Cadena, y luego se definen dos variables (e y s) de esos tipos y se las usa.

testType.pas

   1:
   2:type
   3:   Entero = integer;
   4:   Cadena = string[20];
   5:
   6:var
   7:   // defino una variable de tipo Entero
   8:   e:Entero;
   9:
  10:   // defino una variable de tipo Cadena
  11:   s:Cadena;
  12:
  13:begin
  14:   e:=10;
  15:   s:='Prueba';
  16:
  17:   writeln(e,' ',s);
  18:end.
  19:

En este capítulo nos interesa definir tipos de datos compuestos, es decir: tipos de datos que agrupen dos o más datos simples.


Registros

Llamamos registro o estructura a un tipo de datos definido por el programador que agrupa dos o más datos relacionados entre sí, a los que llamaremos campos.

Veamos un programa que define un registro RAlumno que contiene 3 campos: legajo, nombre y fecNac.

testRecord.pas

   1:
   2:type
   3:
   4:   // definimos un nuevo tipo de datos
   5:   // un "registro"
   6:   RAlumno = record
   7:      legajo: integer;
   8:      nombre: string[20];
   9:      fecNac: longint; // aaaammdd
  10:   end;
  11:
  12:var alumno:RAlumno;
  13:
  14:begin
  15:   // leemos el legajo
  16:   write('Ingrese Legajo: ');
  17:   readln(alumno.legajo);
  18:
  19:   // leemos el nombre
  20:   write('Ingrese Nombre: ');
  21:   readln(alumno.nombre);
  22:
  23:   // leemos la fecha   
  24:   write('Ingrese Fecha (aaaammdd): ');
  25:   readln(alumno.fecNac);
  26:
  27:   // imprimimos los datos
  28:   writeln('Legajo: ',alumno.legajo);
  29:   writeln('Nombre: ',alumno.nombre);
  30:   writeln('Fecha: ',alumno.fecNac);
  31:end.
  32:

Por convensión utilizaremos el prefijo R para indicar que el tipo de datos corresponde a un registro. Por ejemplo: REmpleado, RAlumno, etc.


Analicemos nuevamente el registro RAlumno:

type RAlumno = record
...legajo: integer;
...nombe: string[20];
...fecNac: longint; // aaaammdd
end;

El campo fecNac a su vez podría ser un registro con tres campos: dia, mes y anio. Entonces la sección type quedaría así:

   1:
   2:type
   3:   // definimos un registro RFecha
   4:   RFecha = record
   5:      dia: integer;
   6:      mes: integer;
   7:      anio: integer; // no usamos la "enie"
   8:   end;
   9:
  10:   RAlumno = record
  11:      legajo: integer;
  12:      nombre: string[20];
  13:      fecNac: RFecha; // este campo es tipo RFecha
  14:   end;
  15:

Entonces para asignar la fecha de nacimiento de un alumno (fecNac) será:

   1:
   2:var alumno: RAlumno;
   3:begin
   4:   alumno.fecNac.dia:=2;
   5:   alumno.fecNac.mes:=10;
   6:   alumno.fecNac.anio:=1970;
   7:end.
   8:

Archivos

Llamamos archivo a todo conjunto de datos almacenado en un dispositivo de alacenamiento secundario (no en memoria principal).

La información contenida en un archivo puede ser homogenea o no. Es decir: un archivo puede contener un conjunto de valores integer, un conjunto de valores string, un conjunto de registros de alumnos (RAlumno), etc. Pero tambíen podría contener una combinación arbitraria de diferentes tipos de datos: por ejemplo un integer con un valor n, luego n registros de tipo RAlumno, Luego un longint conteniedo otro valor y así.

En este capítulo estudiaremos archivos homogéneos, principalmente archivos de registros.


Grabar un Archivo

Veamos el código de un programa que lee valores numéricos por teclado y los graba en un archivo llamado SALIDA.dat.

grabarArchivo.pas

   1:
   2:type
   3:   FInteger = file of integer;
   4:
   5:var
   6:   arch: FInteger; // variable de archivo
   7:   v: integer;
   8:begin
   9:   // relacionamos la variable de archivo con
  10:   // el archivo fisico en disco: SALIDA.dat
  11:   assign(arch,'SALIDA.dat');
  12:
  13:   // si el archivo no existe entonces lo crea 
  14:   // si el archivo existe entonces lo vacia
  15:   rewrite(arch);
  16:
  17:   // leemos un valor por teclado (tipo integer)
  18:   read(v);
  19:
  20:   // finalizamos la carga de datos con cero
  21:   while( v <> 0 ) do begin
  22:
  23:      // escribimos en el archivo el valor leido
  24:      write(arch,v);
  25:
  26:      // leemos el siguiente valor (por teclado)
  27:      read(v);
  28:   end;
  29:
  30:   // cierra el archivo
  31:   close(arch);
  32:end.
  33:

Análisis
Analizando el código anterior podremos ver los puntos fundamentales para poder manejar archivos dentro de un programa.

Comenzamos definiendo un tipo de datos propio para el archivo. El tipo FInteger. Por convensión utilizaremos el prefijo F para identificar los tipos de datos que se refieren a archivos.
Recordemos que el archivo contendrá valores numéricos ingresados por teclado. Así que un archivo de integer estará bien (siempre que no se ingresen valores con decimales o valores mayores que 32767). También definimos una variable del tipo FInteger. La variable arch.

   1:
   2:type
   3:   FInteger = file of integer;
   4:
   5:var
   6:   arch: FInteger; // variable de archivo
   7:   v: integer;
   8:

Teniendo definido el tipo del archivo y una variable de ese tipo para manejarlo tenemos que relacionar la variable de archivo (arch) con un archivo físico en el disco. En el ejemplo el archivo físico será SALIDA.dat. Con la función assign establecemos esta relación y luego con la función rewrite creamos el archivo. Es decir: si no existía lo crea y si existía lo deja vacio (con 0 bytes).

   1:
   2:begin
   3:   // relacionamos la variable de archivo con
   4:   // el archivo fisico en disco: SALIDA.dat
   5:   assign(arch,'SALIDA.dat');
   6:
   7:   // si el archivo no existe entonces lo crea 
   8:   // si el archivo existe entonces lo vacia
   9:   rewrite(arch);
  10:

El próximo paso es leer valores por teclado (finalizando con cero) y grabarlos en el archivo. Para esto utilizamos la función write. Esta función recibe como parámetro la variable de archivo (arch) y el valor que queremos grabar (v). Obviamente el valor tiene que ser del mismo tipo del archivo. Como este archivo es de integer entonces lo que vayamos a grabar en él tiene que ser de tipo integer también.

   1:
   2:   // leemos un valor por teclado (tipo integer)
   3:   read(v);
   4:
   5:   // finalizamos la carga de datos con cero
   6:   while( v <> 0 ) do begin
   7:
   8:      // escribimos en el archivo el valor leido
   9:      write(arch,v);
  10:
  11:      // leemos el siguiente valor (por teclado)
  12:      read(v);
  13:   end;
  14:

Por último es necesario cerrar el archivo. El archivo se abre y se cierra. Para cerrarlo utilizamos la función close.

   1:
   2:   // cierra el archivo
   3:   close(arch);
   4:end.
   5:

Leer un Archivo

Veamos ahora el código de un programa que lee el archivo SALIDA.dat (generado en el problema anterior) y muestra por pantalla su contenido.

leerArchivo.pas

   1:
   2:type
   3:   FInteger = file of integer;
   4:
   5:var
   6:   arch: FInteger;
   7:   v: integer;
   8:begin
   9:   // relaciona la variable de archivo
  10:   // con el archivo fisico SALIDA.dat
  11:   assign(arch,'SALIDA.dat');
  12:
  13:   // abre el archivo
  14:   reset(arch);
  15:
  16:   // mientras no llegue el fin de archivo (eof)
  17:   while( NOT eof(arch) ) do begin
  18:
  19:      // lee el archivo y asigna el valor leido
  20:      // a la variable v (que es del mismo tipo
  21:      // del archivo: integer)
  22:      read(arch,v);
  23:
  24:      // muestro el valor leido
  25:      writeln(v);
  26:   end;
  27:
  28:   // cierra el archivo
  29:   close(arch);
  30:end.
  31:

Análisis
Analizando el código anterior vemos lo siguiente. Para abrir el archivo (luego del assign) utilizamos la funcion reset. Esta función abre para lectura/escritura el archivo pero no borra su contenido.

 1:
 2:type
 3:   FInteger = file of integer;
 4:
 5:var
 6:   arch: FInteger;
 7:   v: integer;
 8:begin
 9:   // relaciona la variable de archivo
10:   // con el archivo fisico SALIDA.dat
11:   assign(arch,'SALIDA.dat');
12:
13:   // abre el archivo
14:   reset(arch);
15:

A continuación iteramos mientras no llegue el fin del archivo. Para esto utilizamos la función eof ("end of file") que retorna true al momento de leer el último registro. Dentro de while leemos con la función read. Esta función recibe la variable de archivo (arch) y una variable del mismo tipo del archivo en la cual va a asignar el valor leido (v).

15:
16:   // mientras no llegue el fin de archivo (eof)
17:   while( NOT eof(arch) ) do begin
18:
19:      // lee el archivo y asigna el valor leido
20:      // a la variable v (que es del mismo tipo
21:      // del archivo: integer)
22:      read(arch,v);
23:
24:      // muestro el valor leido
25:      writeln(v);
26:   end;
27:
28:   // cierra el archivo
29:   close(arch);
30:end.
31:

Veamos los diagramas para los programas grabarArchivo (izquierda) y leerArchivo (derecha).

El Registro Actual y el Fin de Archivo

Cada vez que leemos desde un archivo, la función read leerá (retornará) el próximo registro. Esto es posible porque internamente se maneja un puntero que apunta al siguiente registro que se debe leer.

Cuando hacemos reset el puntero se posiciona en el primer registro. Cuando hacemos read la función retorna el registro apuntado y avanza el puntero al siguiente registro.

Cuando el puntero llega a final del archivo (uno despues del último) la función eof retorna true.

Supongamos que tenemos el archivo NOMBRES.dat (de strings), el siguiente gráfico muestra como se va desplazando el puntero hasta llegar al end of file. En azul se destaca el valor retornado por la función read.

Siguiendo el gráfico paso a paso vemos que al hacer reset el puntero apunta al primer registro. Luego, el primer read retorna 'Analia' y el puntero queda en el segundo registro. El próximo read retorna 'Pablo' y el puntero queda en el tercer registro. El próximo read retorna 'Silvia' y el puntero pasa al fin de archivo (es decir: la función eof da true en ese mismo momento).

Tenemos que tener mucho cuidado al momento de "barrer" un archivo (leerlo integramente desde el primer registro hasta el último) porque la función eof da true al momento de leer el último registro, no luego de leerlo.


Veamos como barrer el archivo NOMBRES.dat sin perder ningún registro.

En el siguiente gráfico el programa de la izquierda está mal, no muestra el último registro. El programa de la derecha es correcto, procesa todos los registros del archivo.

El código Pascal será:

Incorrecto:

1:
2:   // :
3:   read(arch,nom); // leo antes de entrar
4:   while( NOT eof(arch) ) do begin
5:      writeln(nom);
6:      read(arch,nom); // leo antes de cerrar
7:   end;
8:   // :
9:

Leer afuera del while y volver a leer antes de cerrarlo hace que el último registro no se procese. Esto es porque al leer el último registro la función eof retorna true y entonces el while no vuelve a iterar.

Correcto:

11:
12:   // :
13:   while( NOT eof(arch) ) do begin
14:      read(arch,nom); // leo ni bien entra
15:      writeln(nom);
16:   end;
17:   // :
18:
19:

Leer una única vez adentro, al inicio del while, soluciona el problema y permite procesar todos los registros.


El problema del eof puede resultar un poco molesto. En realidad, lo intuitivo (al menos para mi) es que eof de true luego de leerse el último registro, no al mismo momento de leerlo.

Para solucionar esto y poder leer antes de entrar y antes de finalizar el while podemos programar una función (muy simple) que retorne true si llegó el eof y false si no llegó (y en este caso que lea el registro).


El siguiente programa recorre y muestra un archivo de enteros utilizando la función leerArchivo.

leerArchivoConFuncion.pas

   1:
   2:type
   3:   FInteger = file of integer;
   4:
   5:// funcion leerArchivo:
   6:// si es eof retorna true, si no entonces 
   7:// lee el archivo y retorna false
   8:function leerArchivo(var a:FInteger
   9:                   ; var buff:integer): boolean;
  10:begin
  11:   if( eof(a) ) then begin
  12:      leerArchivo:=true;
  13:   end else begin
  14:      read(a,buff);
  15:      leerArchivo:=false;
  16:   end;
  17:end;
  18:
  19:// programa principal
  20:var
  21:   arch: FInteger;
  22:   v: integer;
  23:   fin: boolean;
  24:begin
  25:   assign(arch,'SALIDA.dat');
  26:   reset(arch);
  27:
  28:   // leemos afuera del while utilizando
  29:   // la funcion leerArchivo
  30:   fin:=leerArchivo(arch,v);
  31:
  32:   while( NOT fin ) do begin
  33:      writeln(v);
  34:
  35:      // volvemos a leer antes de cerrar
  36:      // el while utilizando la funcion
  37:      fin:=leerArchivo(arch,v);
  38:   end;
  39:
  40:   close(arch);
  41:end.
  42:

Acceso Directo a Registros

Como ya vimos, al abrir el archivo se maneja un puntero interno que apunta al primer registro. Luego, si leemos ese registro el puntero avanza al próximo registro y así hasta llegar al fin de archivo (eof).

Se puede identificar a los registros por la posición que ocupan dentro del archivo y luego posicionar el puntero para acceder y leer directamente el registro ubicado en dicha posición.

Para esto disponemos de las siguientes funciones:

• fileSize(arch) - retorna la cantidad de registros que tiene el archivo
• seek(arch,n) - posiciona el puntero en el registro número n
  

El siguiente programa utiliza la funcionalidad de acceso directo para leer arbitrariamente los registros del archivo PERSONAS.dat. El usuario ingresa el número de registro que quiere ver y el programa lo muestra. Así hasta que se ingrese un número de registro negativo.

testAccesoDirecto.pas

   1:
   2:type
   3:   RPersona = record
   4:      nombre: string[20];
   5:      edad: integer;
   6:   end;
   7:   FPersona = file of RPersona;
   8:
   9:// programa principal
  10:var
  11:   arch: FPersona;
  12:   reg: RPersona;
  13:   cantReg,pos: integer;
  14:begin
  15:   // abro el archivo para leerlo
  16:   assign(arch,'PERSONAS.dat');
  17:   reset(arch);
  18:
  19:   // obtengo la cantidad de registros que 
  20:   // tiene el archivo
  21:   cantReg:=filesize(arch);
  22:   writeln('El archivo tiene: '
  23:            , cantReg,' registros.');
  24:
  25:   // el usuario ingresa el nro. de registro 
  26:   // que quiere leer
  27:   write('Ingrese Nro. Registro (0,'
  28:            , cantReg-1,'): ');
  29:   readln(pos);
  30:
  31:   while( pos >= 0 ) do begin
  32:
  33:      // posiciono el puntero 
  34:      seek(arch,pos);
  35:
  36:      // leo el registro apuntado por el puntero
  37:      read(arch,reg);
  38:
  39:      // muestro la informacion
  40:      writeln( reg.nombre,' , ', reg.edad );
  41:
  42:      // vuelvo a pedir al usuario que 
  43:      // ingrese el proximo nro. de registro
  44:      write('Ingrese Nro. Registro (0,'
  45:            , cantReg-1,'): ');
  46:      readln(pos);
  47:   end;
  48:
  49:   close(arch);
  50:end.
  51:

Notemos que la posición de los registros se cuenta a partir de 0 (cero). Por este motivo la función seek puede posicionarse entre los registros 0 y n-1 (siendo n la cantidad de registros del archivo).

Es decir: si filesize(arch) = n entonces seek(arch,0) posiciona el puntero en el primer registro, seek(arch, 1) posiciona el puntero en el segundo registro y... seek(arch,n-1) posiciona el puntero en el último registro.

Veamos el diagrama:

Ordenamiento de Archivos

Lamentablemente no hay forma de ordenar los registros de un archivo sin que esto implique reescribir nuevamente el archivo. Es decir: ordenar un archivo implica escribirlo de nuevo.

Por esto (sobre todo para archivos grandes) el proceso de ordenamiento suele ser costoso (en términos de procesamiento). Debemos ser prudentes al momento de considerarlo como una opción válida.


Ordenar Archivos vía Arrays

Esta opción solo es válida para archivos pequeños y (dado que la longitud del array debe ser definida con anticipación) con una cantidad de registros acotada.

La idea es: definir un array de registros del mismo tipo que los registros del archivo, "subir" el archivo al array, ordenar el array y "bajar" el array al archivo, reescribiéndolo.

El término "subir" describe la acción de cargar (en este caso) en el array los registros leidos del archivo. El término "bajar" indica la acción de grabar los registros del array en el archivo.


Supongamos que el archivo PERSONAS.dat tiene a lo sumo 100 registros, entonces el siguiente programa nos permite ordenarlo ascendentemente por el campo nombre.

Comencemos por analizar la sección type en la que definiremos el tipo de registro, el tipo del archivo y un tipo ARPersona como un array de registros RPersona, de 100 posiciones.

 1:
 2:type
 3:   RPersona = record
 4:      nombre: string[20];
 5:      edad: integer;
 6:   end;
 7:   FPersona = file of RPersona;
 8:
 9:   // un array de 100 registros RPersona
10:   ARPersona = array [1..100] of RPersona;
11:

Con la sección type definida, veamos el diagrama del algoritmo que resuelve el problema y luego continuaremos con el resto del código.

Para resolver el problema abrimos el archivo, lo subimos al array con la función subirArchivo, ordenamos el array con el procedimiento ordenar, vaciamos el archivo con rewrite y bajamos al archivo el contenido del array (con el procedimiento bajarArchivo).

Notemos que la función subirArchivo retorna un entero (len) que indica la cantidad de elementos útiles que se insertaron en el array.

Que el array sea de 100 elementos no significa que los 100 elementos estén siendo utilizados. Lo definimos de 100 porque ese es el número máximo de registros que puede tener el archivo (según el enunciado). Pero si el archivo tiene 20 registros entonces len (el valor de retorno de la función) será 20.


Ahora si, continuemos con el código del programa.

function subirArchivo

13:
14:function subirArchivo(var a:FPersona
15:                    ; var arr: ARPersona): integer;
16:var reg:RPersona; i:integer;
17:begin
18:   i:=0;
19:   while( NOT eof(a) ) do begin
20:      read(a,reg);
21:      i:=i+1;
22:      arr[i]:=reg;
23:   end;
24:
25:   subirArchivo:=i;
26:end;
27:

La función recorre el archivo (lo recibe abierto), asigna al array en la posición i el registro leido (reg) e incrementa el valor de i. Es decir que al finalizar el while, en i tendremos la cantidad de registros que se insertaron en el array. Por eso el valor de retorno será i.

procedure ordenar

28:
29:procedure ordenar(var arr:ARPersona; len: integer);
30:var ordenado: boolean; i:integer; aux: RPersona;
31:begin
32:   ordenado:= false;
33:   while( NOT ordenado ) do begin
34:      ordenado:=true;
35:      for i:=1 to len-1 do begin
36:         if(arr[i+1].nombre<arr[i].nombre) then begin
37:            aux:=arr[i];
38:            arr[i]:=arr[i+1];
39:            arr[i+1]:=aux;
40:            ordenado:=false;
41:         end;
42:
43:      end;
44:   end;
45:end;
46:

Simplemente es el procedimiento de la burbuja adaptado para el tipo de datos de los elementos del array (RPersona).

procedure bajarArchivo

48:
49:procedure bajarArchivo( var a:FPersona
50:                      ; var arr: ARPersona
51:                      ; len: integer);
52:var reg:RPersona; i:integer;
53:begin
54:   for i:=1 to len do begin
55:      write(a,arr[i]);
56:   end;
57:end;
58:

Recorre el array y graba en el archivo (abierto y vacio) cada uno de los registros del array. Recordemos que tanto el array como el archivo contienen registros del mismo tipo: RPersona.

programa principal

60:
61:// programa principal
62:var arch: FPersona; arr: ARPersona; len: integer;
63:begin
64:   // abro el archivo
65:   assign(arch,'PERSONAS.dat');
66:   reset(arch);
67:
68:   // lo subo a un array de registros
69:   len:=subirArchivo(arch,arr);
70:
71:   // ordeno el array
72:   ordenar(arr,len);
73:
74:   // reescribo el archivo
75:   rewrite(arch);
76:
77:   // grabo en el archivo los registros del array
78:   bajarArchivo(arch,arr,len);
79:
80:   close(arch);
81:end.
82:

Búsqueda Binaria sobre Archivos

Si el archivo se encuentra ordenado por el campo por el cual queremos buscar, entonces podemos aplicar el algoritmo de la búsqueda binaria exactamente de la misma manera que lo utilizamos para realizar búsquedas sobre arrays.


Supongamos que tenemos el archivo EMPLEADOS.dat ordenado por el campo legajo con el siguiente formato de registro:

REmpleado = record
..legajo: integer;
..nombre: string[20];
end;

Entonces podemos analizar la función buscarBinArch que realiza una búsqueda binaria sobre este archivo y retorna (en un valor entero) la posición del registro que contiene el valor (legajo) que estamos buscando (si existe) o un valor negativo si no existe lo que buscamos.

   1:
   2:function buscarBinArch(var arch: FEmpleado
   3:                     ; v:integer
   4:                     ; var reg: REmpleado): integer;
   5:var i,j,k: integer; encontrado: boolean;
   6:begin
   7:
   8:   encontrado:=false;
   9:
  10:   // i comeinza en cero (primer posicion)
  11:   i:=0;
  12:
  13:   // j apunta al ultimo registro (recordemos que 
  14:   // se numeran desde cero)
  15:   j:=filesize(arch)-1;
  16:
  17:   while( (i<=j) AND (NOT encontrado) ) do begin
  18:
  19:      // calculo la posicion promedio
  20:      k:= (i+j) div 2;
  21:
  22:      // posiciono el puntero y leo
  23:      seek(arch,k);
  24:      read(arch,reg);
  25:
  26:      if( reg.legajo = v ) then begin
  27:         encontrado:=true;
  28:      end else begin
  29:         if( reg.legajo < v ) then begin
  30:            i:=k+1;
  31:         end else begin
  32:            j:=k-1;
  33:         end;
  34:      end;
  35:   end;
  36:
  37:   if( i>j ) then begin
  38:      buscarBinArch:=-1;
  39:   end else begin
  40:      buscarBinArch:=k;
  41:   end;
  42:end;
  43:

Comparando con la búsqueda binaria sobre arrays las únicas diferencias son:

1 - j se inicializa con la posición del último registro del archivo (menos 1 porque los registros se numeran desde cero) y
2 - Luego de calcular el valor de k hacemos un acceso directo al archivo para leer el registro ubicado en esa posición.

Notemos que el parámetro reg lo recibimos por referencia por lo tanto cuando leemos en el archivo y utilizamos esta variable para que la función read guarde allí lo que leyó, los datos leidos quedarán en la variable aún despues de finalizar la función buscarBinArch.


Ahora veamos un programa principal que le pide al usuario que ingrese legajos y (si existen) muestra los datos completos del registro encontrado.

   1:
   2:// programa principal
   3:var pos,leg:integer; arch: FEmpleado; reg: REmpleado;
   4:begin
   5:   assign(arch,'EMPLEADOS.dat');
   6:   reset(arch);
   7:
   8:   write('Legajo: ');
   9:   readln(leg);
  10:
  11:   while( leg > 0 ) do begin
  12:
  13:      // busqueda binaria sobre el archivo
  14:      pos:=buscarBinArch(arch,leg,reg);
  15:      if( pos >= 0 ) then begin
  16:         writeln( 'Encontrado (',pos,'): '
  17:                  , reg.legajo,' , '
  18:                  , reg.nombre);
  19:      end else begin
  20:         writeln( 'Legajo no encontrado');
  21:      end;
  22:
  23:      write('Legajo: ');
  24:      readln(leg);
  25:   end;
  26:
  27:   close(arch);
  28:end.
  29:

Notemos que la función buscarBinArch retorna un entero positivo indicando en que posición fué encontrado el registro cuyo campo legajo es el que estamos buscando. Si la función retorna un valor negativo significa que no se encontró ningún registro con ese legajo.

Si el registro se encontró entonces la misma función ya deja cargados los datos del registro en la variable reg.

Indexar Archivos

Como dijimos anteriormente, no siempre es una buena idea ordenar el archivo. Y si el archivo no está ordenado entonces no se puede realizar una búsqueda binaria sobre él. Tenemos un problema.

La solución consiste en crear un índice ordenado por el campo por el cual queremos realizar la búsqueda y luego acceder a los registros del archivo de manera directa, previa búsqueda sobre el índice.

El índice se puede implementar en un array (si la cantidad de registros del archivo está acotada) o en una lista enlazada.

Implementando el Indice sobre un Array

Veremos como implementar el índice para el archivo EMPLEADOS.dat sobre un array (arrIndice).

Supongamos que el archivo EMPLEADOS.dat tiene a lo sumo 100 registros. Entonces definiremos un registro RIndice y un array (arrIndice) de 100 elementos tipo RIndice:

type
..// definimos el registro para el indice
..RIndice = record
....legajo: integer;
....posArch: integer;
..end;

..// definimos tipo para el array
..ARIndice = array [1..100] of RIndice;

var
..arrIndice: ARIndice; // definimos el array

La idea es recorrer el archivo e ir insertando registros en el array ordenados por el campo legajo (que es el campo clave para la búsqueda), guardando en el campo posArch la posición que ocupa dentro del archivo el registro que tiene ese legajo.

En el ejemplo vemos que el array quedó ordenado por legajo. Así podremos realizar una búsqueda binaria sobre el array para buscar (por ejemplo) el legajo número 271. Cuando lo encontremos veremos que el campo posArch dirá 1. Entonces si accedemos al archivo, al registro número 1 habremos encontrado el registro que estábamos buscando.

Analicemos entonces la función indexaEmpleados que lee el archivo y genera el array índice sobre el que luego se podrá realizar la búsqueda binaria por la clave legajo.

Primero veamos la sección type donde definimos los tipos REmpleado (registros del archivo), FEmpleado (tipo del archivo), RIndice (registros del array) ARIndice (tipo que define un array de 100 RIndice).

 1:
 2:type
 3:   REmpleado = record
 4:      legajo: integer;
 5:      nombre: string[20];
 6:   end;
 7:
 8:   FEmpleado = file of REmpleado;
 9:
10:   RIndice = record
11:      legajo: integer;
12:      posArch: integer; // posicion en el archivo 
13:   end;
14:
15:   ARIndice = array [1..100] of RIndice;
16:

Veamos ahora la función indexarEmpleados. Esta función recibe el archivo arch (ya abierto) y el array arr (vacio, sin elementos). Retorna la cantidad de elementos útiles que se insertaron en el array (len).

El objetivo de la función es recorrer el archivo arch y por cada registro del archivo ir insertando (ordenado por legajo) registros (de tipo ARIndice) en el array arr.

51:
52:function indexarEmpleados(var arch:FEmpleado
53:                         ;var arr:ARIndice): integer;
54:var len:integer;reg:REmpleado;regArr:RIndice;
55:begin
56:   len:=0;
57:   while( NOT eof(arch) ) do begin
58:      read(arch,reg);
59:      regArr.legajo:=reg.legajo;
60:      regArr.posArch:=len;
61:
62:      insertarOrdenado(arr,len,regArr);
63:   end;
64:
65:   indexarEmpleados:=len;
66:end;
67:

Como vemos, el algoritmo que resuelve la función es muy simple: recorre el archivo, por cada registro del archivo asigna el legajo y la posición en el archivo del registro leido (que coincide con len) en un registro de tipo RIndice. Luego, utilizando la función insertarOrdenado inserta ese registro en el array.

Cabe aclarar que en este caso la función insertarOrdenado fue modificada. El array que recibe es de tipo ARIndice y el valor que recibe para insertar es de tipo RIndice. Y en todas las condiciones lógicas pregunta por arr[i].legajo o valor.legajo ya que legajo es el campo clave.

Veamos el código del procedimiento insertar y de la función insertarOrdenado adaptados para este problema.

17:
18:procedure insertar(var arr: ARIndice
19:                 ; var len: integer
20:                 ; valor: RIndice; pos: integer);
21:var i: integer;
22:begin
23:   for i:=len+1 downto pos+1 do begin
24:      arr[i]:= arr[i-1];
25:   end;
26:
27:   arr[pos]:=valor;
28:   len:=len+1;
29:end;
30:
31:function insertarOrdenado(var arr: ARIndice
32:                        ; var len: integer
33:                        ; valor: RIndice): integer;
34:var i:integer;
35:begin
36:   i:=1;
37:   while( (i<= len) AND (arr[i].legajo<=valor.legajo))
38:   do begin
39:      i:=i+1;
40:   end;
41:
42:   if( i>len ) then begin
43:      len:=len+1;
44:      arr[len]:=valor;
45:      insertarOrdenado:=len;
46:   end else begin
47:      insertar(arr,len,valor,i);
48:      insertarOrdenado:=i;
49:   end;
50:end;
51:

Ahora podemos ver el programa principal. Pide al usuario que ingrese un legajo, lo busca en el índice y (si existe) accede directamente al archivo para leer y mostrar los datos del empleado.

El código del programa principal es:

 97:
 98:// programa principal
 99:var
100:   arch:FEmpleado ;
101:   arrIndice:ARIndice;
102:   reg:REmpleado;
103:   len,leg,posArr,posArch:integer;
104:
105:begin
106:   assign(arch,'EMPLEADOS.dat');
107:   reset(arch);
108:
109:   len:=indexarEmpleados(arch,arrIndice);
110:
111:   write('Ingrese Legajo: ');
112:   readln(leg);
113:
114:   while( leg>0 ) do begin
115:
116:      posArr:=buscarBinIndex(arrIndice,len,leg);
117:
118:      if( posArr>0 ) then begin
119:         posArch:=arrIndice[posArr].posArch;
120:         seek(arch,posArch);
121:         read(arch,reg);
122:         writeln('Legajo: ',reg.legajo
123:               ,' Nombre: ',reg.nombre);
124:      end else begin
125:         writeln('Legajo no encontrado');
126:      end;
127:
128:      write('Ingrese Legajo: ');
129:      readln(leg);
130:   end;
131:   close(arch);
132:end.
133:

Inplementando el Indice sobre una Lista Enlazada

Esta técnica la estudiaremos en el capítulo de Estructuras Dinámicas, luego de analizar los temas de punteros y listas.


Apareo de Archivos

Se considera "apareo de archivos" a los problemas que intercalan datos de dos o más archivos que se encuentran ordenados por la misma clave, recorriéndolos simultaneamente.

Analicemos los datos de los siguientes conjuntos:

Los dos conjuntos están ordenados en forma ascendente. Leemos el primer valor de A (lo llamaremos a) y luego el primer valor de B (lo llamaremos b).

Si a(1) < b(2) podemos determinar que el valor a está en el conjunto A pero no en el conjunto b, ya que como están ordenados el siguiente valor de B será aún más grande. Luego leemos el siguiente valor de A a(3) y lo comparamos con b(2).

Si a(3) > b(2) entonces podemos determinar que el valor de b(2) está en el conjunto B pero no en el conjunto A. Ahora leemos B b(3).

Si a(3) = b(3) entonces el valor se encuentra en ambos conjuntos. En este caso leemos A y B y así sucesivamente hasta que finalice alguno de los dos conjuntos.

Si un conjunto (A) termina antes que el otro (B) podemos asegurar que todos los elementos sobrantes (de B) no estarán contenidos en el otro conjunto (A).

Luego de este análisis podemos plantear un enunciado que le de sentido a lo anterior.


Problema 6.1
Se tienen los archivos PRESTA_2006.dat y PRESTA_2007.dat, con la información correspondiente a las prestaciones que realizaron los diferentes médicos de una clínica. Ambos archivos están ordenados por id_medico y tienen los siguientes campos:

• id_medico (5 dígitos)
• cantidad (4 dígitos)
  

Existe la posibilidad de que durante el año 2007 se hayan incorporado médicos que no trabajaron durante 2006. También pueden haber médicos que trabajaron durante 2006 pero no durante 2007.

Se Pide

1. Un listado de los médicos que se incorporaron durante 2007 (no serán más de 100).
2. Un listado de los médicos que solo trabajaron durante 2006 (no serán más de 100).
3. Un listado indicando los médicos que incrementaron la cantidad de prestaciones de un año al otro.
   

Análisis
La idea del apareo de archivos es recorrer simultaneamente ambos archivos comparando su campo clave (por el cual están ordenados). Si encontramos un registro en PRESTA_2006 que no está en PRESTA_2007 corresponderá a un médico que no trabajó en 2007. Si encontramos un registro en PRESTA_2007 que no está en PRESTA_2006 entonces ese médico se incorporó en 2007. Si encontramos un mismo id_medico en ambos archivos entonces ese médico trabajó en 2006 y 2007.

Veamos el siguiente ejemplo (los datos de la izquierda corresponden a PRESTA_2006. Los de la derecha corresponden a PRESTA_2007):

Leemos ambos archivos y comparamos su id_medico. Si coinciden entonces ese id_medico corresponde a un médico que trabajó en los años 2006 y 2007. Leemos nuevamente en los dos archivos:

Ahora id_medico en PRESTA_2006 es mayor que id_medico en PRESTA_2007. Evidentemente el médico con id_medico=2 se incorporó en 2007. En este caso leemos solamente PRESTA_2007.

Ahora en los dos archivos tenemos registros con el mismo id_medico (3). Este médico también trabajó los dos años. Volvemos a leer ambos archivos.

En este caso id_medico en PRESTA_2006 es menor que id_medico en PRESTA_2007. Esto significa que el médico con id_medico=4 no trabajó en 2007. En este caso solo leemos PRESTA_2006 y así hasta el fin de datos de alguno de los dos archivos.

Si llega el fin de datos de PRESTA_2006 significa que todos los registros que quedan por leer en PRESTA_2007 corresponden a médicos que se incorporaron ese año. Pero si llega primero el eof de PRESTA_2007 entonces todos los registros que quedan sin leer en PRESTA_2006 corresponden a médicos que dejaron de trabajar.


La estrategia de solución será la siguiente: tendremos dos arrays (arr06 y arr07) de 100 elementos cada uno. En arr06 iremos guardando los médicos que solo trabajaron en 2006 (punto 2 del enunciado). En arr07 iremos guardando los médicos que se incorporaron a trabajar en 2007 (punto 1 del enunciado). Los médicos que trabajaron los dos años e incrementaron la cantidad de prestaciones (punto 3 del enunciado) los listaremos a medida que los encontremos.

Veamos la sección type para definir los tipos de datos.

   1:
   2:type
   3:   // registro de los archivos
   4:   RPresta = record
   5:      id_medico: longint;
   6:      cantidad: integer;
   7:   end;
   8:
   9:   // tipo para los archivos
  10:   FPresta = file of RPresta;
  11:  
  12:   // tipo para los arrays de medicos
  13:   AMed = array [1..100] of longint;
  14:

En el programa principal resolvemos el apareo de archivos. Leemos PRESTA_2006 y PRESTA_2007 e iteramos mientras no llegue el fin de archivo de alguno de los dos. Comparamos reg06.id_medico con reg07.id_medico:

• Si reg06.id_medico = reg07.id_medico entonces tenemos que comparar las prestaciones que realizó ese médico durante 2006 y 2007. Si las de 2007 fueron más entonces lo imprimimos para resolver el punto 3 del eununciado. Luego volvemos a leer los dos archivos.
• Si reg06.id_medico > reg07.id_medico entonces el médico apuntado en PRESTA_2007 es nuevo, se incorporó ese año. Almacenamos su id_medico en el array arr07.
• Si reg06.id_medico no es mayor que reg07.id_medico entonces el médico apuntado en PRESTA_2006 no trabajó durante 2007. Almacenamos su id_medico en el array arr06.
  

Por último, preguntamos cual de los dos archivos terminó. Si termino PRESTA_2006 tenemos que recorrer PRESTA_2007 hasta el final agregando todos los registros que quedaron en arr07 ya que todos fueron médicos que se incorporaron ese año. Si el que terminó primero fue PRESTA_2007 entonces recorremos hasta el final PRESTA_2006 agregando todos los registros que quedarón en arr06 porque todos corresponden a médicos que dejaron de trabajar.

Algoritmos y Estructuras de Datos UTN - UBA.