PDF de programación - Parte VI - Estructura de datos en C, C++ y Java

Parte VI

Estructura de datos
en C, C++ y Java

31

Capítulo

Organización
de datos
en un archivo

Contenido

•
•
•
•
•
•
•
•
•

hash

Registros
Organización de archivos
Archivos con función de direccionamiento
Archivos secuenciales indexados
Ordenación de archivos: ordenación externa
Codificación del algoritmo de mezcla directa
Resumen
Ejercicios

Problemas

Introducción
Grandes cantidades de datos se almacenan nor malmente en dispositivos de memoria externa. En este
capítulo se realiza una introducción a la organi zación y gestión de datos estructurados sobre dis­
positivos de almacenamiento secundario, tales como discos magnéticos, CD... Las técnicas requeridas
para gestionar datos en archivos son diferentes de las técnicas que estructuran los datos en memoria
principal, aunque se construyen con ayuda de estructuras utilizadas en esta memoria.

Los algoritmos de ordenación de arrays no se pueden aplicar, normalmente, si la cantidad de datos
a ordenar no caben en la memoria principal de la computadora y están en un dispositivo de almacena­
miento externo. Es necesa rio aplicar nuevas técnicas de ordenación que se complementen con las ya
estudiadas. Entre las téc nicas más importantes destaca la fusión o mezcla. Mezclar significa combinar
dos (o más) secuencias en una sola secuencia ordenada por medio de una selección repetida entre los
componentes accesi bles en ese momento.

934

Capítulo 31

Organización de datos en un archivo

Conceptos clave

•
•
•
•
•

Archivo secuencial
Archivo secuencial indexado
Colisión
Dirección dispersa
Hash



• Mezcla
• Ordenación externa
• Registro
• Secuencia
• Transformación de claves

Registros
Un archivo o fichero es un conjunto de datos estructurados en una colección de registros, que son de
igual tipo y constan a su vez de diferentes entidades de nivel más bajo denominadas campos.

Un registro es una colección de campos lógicamente relacionados, que pueden ser tratados como
una unidad por algún programa. Un ejemplo de un registro puede ser la información de un determina­
do libro que contiene los campos de título, autor, editorial, fecha de edición, número de páginas,
ISBN, etc. Los regis tros organizados en campos se denominan registros lógicos.

El concepto de registro es similar al concepto de estructura (struct) de C. Una posible representa­

ción en C del registro libro es la siguiente:

struct libro
{
char titulo [46];
char autor [80];
char editorial [35];
struct fecha fechaEdicion;
int numPags;
long isbn;
};


A recordar

El número de registros lógicos que puede conte-
ner un registro físico se denomina factor de
blo queo. Las operaciones de entrada/salida que
se realizan en programas C se hacen por blo-
ques a través de un área de memoria principal
denominada buffer; esto hace que mejore el
rendimiento de los programas.
La constante predefinida BUFSIZ
(stdio.h) contiene el tamaño del buffer.

Clave
Una clave es un campo de datos que identifica el registro y lo diferencia
de otros registros. Normalmente los registros de un archivo se organizan
según un campo clave. Claves típicas son números de identifica ción,
nombres; en general puede ser una clave de cualquier campo que admi­
ta relaciones de comparación. Por ejemplo, un archivo de libros puede
estar organizado por autor, por editorial, etcétera.

Registro físico (bloque)
Un registro físico o bloque es la cantidad de datos que se transfieren en
una operación de entrada/salida entre la memoria central y los disposi­
tivos periféricos.

Un bloque puede contener uno o más registros lógicos. También pue­

de ser que un registro lógico ocu pe más de un registro físico o bloque.

Organización de archivos

La organización de un archivo define la forma en que los registros se disponen sobre el dispositivo de
alma cenamiento. La organización determina cómo estructurar los registros en un archivo. Se conside­
ran tres organizaciones fundamentales:

•
•
•

Organización secuencial.
Organización directa.
Organización secuencial indexada.

Organización de archivos

935

Organización secuencial
Un archivo con organización secuencial (archivo secuencial) es una sucesión de registros almacena­
dos consecutivamente, uno detrás de otro, de tal modo que para acceder a un registro dado es necesa­
rio pasar por todos los registros que le preceden.

En un archivo secuencial los registros se insertan en orden de llegada, es decir, un registro se
almace na justo a continuación del registro anterior. Una vez insertado el último registro y cerrado el
archivo, el sistema añade la marca fin de archivo.

Las operaciones básicas que se realizan en un archivo secuencial son: escribir los registros, con-

sultar los registros y añadir un registro al final del archivo.

Un archivo con organización secuencial se puede procesar tanto en modo texto como en modo
bina rio. En C para crear estos archivos se abren (fopen ( )) especificando en el argumento modo:
"w", "a", "wb" o "ab"; a continuación se escriben los registros utilizando, normalmente, las funcio­
nes fwrite ( ), fprintf ( ) y fputs ( ).

La consulta del archivo se realiza abriendo éste con el modo "r" y, generalmente, leyendo todo
el archivo hasta el indicador o marca fin de archivo. La función feof ( ) es muy útil para detectar el
fin de archivo, devuelve 1 si se ha alcanzado el final del archivo. El siguiente bucle permite leer to­
dos los regis tros del archivo:

while (!feof(pf))
{
< leer registro >
}



Ejercicio 31.1

Se realizan votaciones para elegir al presidente de la federación de Petanca. Cada distrito envía a la
ofi cina central un sobre con los votos de cada uno de los tres candidatos. En un archivo con organi-
zación secuencial se graban registros con la estructura de datos correspondiente a cada distrito, es
decir: nom bre del distrito y votos de cada candidato. Una vez terminado el proceso de grabación se
han de obtener los votos de cada candidato.
Los campos de datos que tiene cada uno de los registros están descritos en el propio enunciado:
Nom bre del distrito, Candidato1, votos, Candidato2, votos y Candidato3, votos. El archivo es de tipo
binario; de esa forma se ahorra convertir los datos de tipo entero (votos) a dígitos ASCII, y cuando se
lea el archi vo para contar votos hacer la conversión inversa.
La creación del archivo se hace abriendo éste en modo añadir al final ("a"); de esta forma pueden
aña dirse nuevos registros en varias sesiones.
Para realizar la operación de cuenta de votos es necesario, en primer lugar, abrir el archivo en modo
lectura ("rb"), y en segundo lugar leer todos los registros hasta llegar a la marca de fin de archivo.
Con cada registro leído se incrementa la cuenta de votos de cada candidato.
La declaración del registro, en este ejercicio, se denomina Distrito, el nombre del archivo y la
defi nición del puntero a FILE se realiza en el archivo Petanca.h:

typedef struct
{
char candidato1[41];
long vot1;
char candidato2 [41];
long vot2;
char candidato3 [41];
long vot3;
} Distrito;

char* archivo = "Petanca.dat";
FILE *pf = NULL;

936

Capítulo 31

Organización de datos en un archivo

/*
Código fuente del programa, petanca.c, que escribe secuencialmente los
registros en el archivo Petanca.dat.
*/

void main ( )
{
Distrito d;
int termina;
pf = fopen (archivo, "ab");
if (pf == NULL)
{
puts ("No se puede crear el archivo.");
exit(−1);
}

strcpy(d.candidato1, "Lis Alebuche");
strcpy(d.candidato2, "Pasionis Cabitorihe");
strcpy(d.candidato3, "Gulius Martaria");
termina = 0;
puts ("Introducir los votos de cada candidato, termina con 0 0 0");
do {
leeRegistro (&d);
if ( (d.vot1 == 0) && (d.vot2 == 0) && (d.vot3 == 0))
{
termina = 1;
puts ("Fin del proceso. Se cierra el archivo");
}
else
fwrite(&d, sizeof(Distrito), 1, pf);
} while (!termina);
fclose(pf);
}

void leeRegistro(Distrito* d)
{
printf ("Votos para %s : ", d −> candidato1);
scanf("%ld", &(d −> vot1));
printf ("Votos para %s : ", d −> candidato2);
scanf("%ld", &(d −> vot2));
printf ("Votos para %s : ", d −> candidato3);
scanf("%ld", &(d −> vot3));
}

/*
Código fuente del programa, cntavoto.c, que lee secuencialmente los registros
del archivo Petanca.dat y cuenta los votos.
*/

#include <stdlib.h>
#include <stdio.h>
#include <string .h>
#include "petanca. h"
void main ( )
{
Distrito d;
int votos[3] = {0,0,0};

pf = fopen(archivo, "rb");
if (pf == NULL)
{
puts("No se puede leer el archivo.");
exit(−1);
}
fread (&d, sizeof(Distrito),1, pf);

Organización de archivos

937

while (!feof(pf))
{
votos[0] += d.vot1;
votos[1] += d.vot2;
votos[2] += d.vot3;
fread(&d, sizeof(Distrito),1, pf);
}
fclose(pf);
puts (" \n\tVOTOS DE CADA CANDIDATO\n");
printf (" %s %ld: \n", d.candidato1, votos [0] );
printf (" %s %ld: \n", d.candidato2, votos [1] );
printf (" %s %ld: \n", d.candidato3, votos [2] );
}

Organización directa
Un archivo con organización directa (aleatoria), o sencillamente archivo directo, se caracteriza por­
que el acceso a cualquier registro es directo mediante la especificación de un índice, que da la posi­
ción ocupada por el registro respecto al origen del archivo.

Los archivos directos tienen una gran rapidez para el acceso a los registros comparados con los
secuen ciales. La lectura/escritura de un registro es rápida, ya que se accede directamente al registro y
no se nece sita recorrer los anteriores, como ocurre en los archivos secuenciales.

En C estos archivos pueden ser de texto o binarios. Normalmente se crean de tipo binario para que
las operaciones de entrada/salida sean más eficientes. C dispone de funciones para situarse, o cono­
cer la posición en el archivo: fseek ( ), fsetpos ( ), ftell ( ) y fgetpos ( ).

Los registros de los arch