Fundamentos de Programación (ARCHIVOS) - Joyanes Aguilar - PDF

FUNDAMENTOS DE PROGRAMACIÓN Algoritmos, estructura de datos y objetos Cuarta edición Luis Joyanes Aguilar Catedrático de Lenguajes y Sistemas Informáticos Facultad de Informática, Escuela Universitaria de Informática Universidad Pontificia de Salamanca campus de Madrid MADRID BOGOTÁ BUENOS AIRES CARACAS GUATEMALA LISBOA MÉXICO NUEVA YORK PANAMÁ SAN JUAN SANTIAGO S ÃO PAULO AUCKLAND HAMBURGO LONDRES MILÁN MONTREAL NUEVA DELHI PARÍS SAN FRANCISCO SIDNEY SINGAPUR ST LOUIS TOKIO TORONTO CAPÍTULO 9 Archivos (ficheros) 9.1. Archivos y flujos (stream): La jerarquía de 9.10. Procesamiento de archivos directos (algo- datos ritmos) 9.2. Conceptos y definiciones = terminología 9.11. Procesamiento de archivos secuenciales 9.3. Soportes secuenciales y direccionables indexados 9.4. Organización de archivos 9.12. Tipos de archivos: consideraciones prácticas 9.5. Operaciones sobre archivos en C/C++ y Java 9.6. Gestión de archivos ACTIVIDADES DE PROGRAMACIÓN RESUELTAS 9.7. Flujos CONCEPTOS CLAVE 9.8. Mantenimiento de archivos RESUMEN 9.9. Procesamiento de archivos secuenciales EJERCICIOS (algoritmos) INTRODUCCIÓN Los datos que se han tratado hasta este capítulo y namiento secundario, tales como cintas y discos mag- procesados por un programa pueden residir simultá- néticos. Estas colecciones de datos se conocen como neamente en la memoria principal de la computadora. archivos (ficheros). Las técnicas requeridas para ges- Sin embargo, grandes cantidades de datos se alma- tionar archivos son diferentes de las técnicas de orga- cenan normalmente en dispositivos de memoria auxi- nización de datos que son efectivas en memoria prin- liar. Las diferentes técnicas que han sido diseñadas cipal, aunque se construyen sobre la base de esas para la estructuración de estas colecciones de datos técnicas. Este capítulo introductorio está concebido complejas se alojaban en arrays; en este capítulo se para la iniciación a los archivos, lo que son y sus mi- realiza una introducción a la organización y gestión siones en los sistemas de información y de los proble- de datos estructurados sobre dispositivos de almace- mas básicos en su organización y gestión. 308 Fundamentos de programación 9.1. ARCHIVOS Y FLUJOS (STREAM): LA JERARQUÍA DE DATOS El almacenamiento de datos en variables y arrays (arreglos) es temporal; los datos se pierden cuando una variable sale de su ámbito o alcance de influencia, o bien cuando se termina el programa. La mayoría de las aplicaciones requieren que la información se almacene de forma persistente, es decir que no se borre o elimine cuando se termina la ejecución del programa. Por otra parte, en numerosas aplicaciones se requiere utilizar grandes cantidades de infor- mación que, normalmente, no caben en la memoria principal. Debido a estas causas se requiere utilizar archivos (ficheros) para almacenar de modo permanente grandes cantidades de datos, incluso después que los programas que crean los datos se terminan. Estos datos almacenados en archivos se conocen como datos persistentes y permanecen después de la duración de la ejecución del programa. Las computadoras almacenan los archivos en dispositivos de almacenamiento secundarios, tales como discos CD, DVD, memorias flash USB, memorias de cámaras digitales, etc. En este capítulo se explicará cómo los programas escritos en un lenguaje de programación crean, actualizan o procesan archivos de datos. El procesamiento de archivos es una de las características más importantes que un lenguaje de programación debe tener para soportar aplicaciones comerciales que procesan, normalmente, cantidades masivas de datos persistentes. La entrada de datos normalmente se realiza a través del teclado y la salida o resultados van a la pantalla. Estas ope- raciones, conocidas como Entrada/Salida (E/S), se realizan también hacia y desde los archivos. Los programas que se crean con C/C++, Java u otros lenguajes necesitan interactuar con diferentes fuentes de datos. Los lenguajes antiguos como FORTRAN, Pascal o COBOL tenían integradas en el propio lenguaje las entra- das y salidas; palabras reservadas como PRINT, READ, write, writeln, etc, son parte del vocabulario del lenguaje. Sin embargo, los lenguajes de programación modernos como C/C++ o Java/C# tienen entradas y salidas en el len- guaje y para acceder o almacenar información en una unidad de disco duro o en un CD o en un DVD, en páginas de un sitio web e incluso guardar bytes en la memoria de la computadora, se necesitan técnicas que pueden ser diferen- tes para diferente dispositivo de almacenamiento. Afortunadamente, los lenguajes citados anteriormente pueden al- macenar y recuperar información, utilizando sistemas de comunicaciones denominados flujos que se implementan en bibliotecas estándar de funciones de E/S (en archivos de cabecera stdio.h y cstdio.h) en C, en una biblioteca estándar de clases (en archivos de cabecera iostream y fstream) en C++, o en el paquete Java.io en el lenguaje Java. Las estructuras de datos enunciadas en los capítulos anteriores se encuentran almacenadas en la memoria central o principal. Este tipo de almacenamiento, conocido por almacenamiento principal o primario, tiene la ventaja de su pequeño tiempo de acceso y, además, que este tiempo necesario para acceder a los datos almacenados en una posición es el mismo que el tiempo necesario para acceder a los datos almacenados en otra posición del dispositivo —memo- ria principal—. Sin embargo, no siempre es posible almacenar los datos en la memoria central o principal de la computadora, debido a las limitaciones que su uso plantea: La cantidad de datos que puede manipular un programa no puede ser muy grande debido a la limitación de la memoria central de la computadora1. La existencia de los datos en la memoria principal está supeditada al tiempo que la computadora está encendi- da y el programa ejecutándose (tiempo de vida efímero). Esto supone que los datos desaparecen de la memoria principal cuando la computadora se apaga o se deja de ejecutar el programa. Estas limitaciones dificultan: La manipulación de gran número de datos, ya que —en ocasiones— pueden no caber en la memoria principal (aunque hoy día han desaparecido las limitaciones que la primera generación de PC presentaba con la limitación de memoria a 640 KBytes, no admitiéndose información a almacenar mayor de esa cantidad en el caso de computadoras IBM PC y compatibles). La transmisión de salida de resultados de un programa pueda ser tratada como entrada a otro programa. 1 En sus orígenes y en la década de los ochenta, 640 K-bytes en el caso de las computadoras personales IBM PC y compatibles. Hoy día esas cifras han sido superadas con creces, pero aunque las memorias centrales varían, en computadoras domésticas, portátiles (laptops) y de es- critorio, entre 1 GB y 4 GB, la temporalidad de los datos almacenados en ellas aconseja siempre el uso de archivos para datos de carácter perma- nente. Archivos (ﬁcheros) 309 Para poder superar estas dificultades se necesitan dispositivos de almacenamiento secundario (memorias externas o auxiliares) como cintas, discos magnéticos, tarjetas perforadas, etc., donde se almacenará la información o datos que podrá ser recuperada para su tratamiento posterior. Las estructuras de datos aplicadas a colección de datos en almacenamientos secundarios se llaman organización de archivos. La noción de archivo o fichero está relacionada con los conceptos de: Almacenamiento permanente de datos. Fraccionamiento o partición de grandes volúmenes de información en unidades más pequeñas que puedan ser almacenadas en memoria central y procesadas por un programa. Un archivo o fichero es un conjunto de datos estructurados en una colección de entidades elementales o básicas denominadas registros o artículos, que son de igual tipo y constan a su vez de diferentes entidades de nivel más bajo denominadas campos. 9.1.1. Campos Un campo es un item o elemento de datos elementales, tales como un nombre, número de empleados, ciudad, núme- ro de identificación, etc. Un campo está caracterizado por su tamaño o longitud y su tipo de datos (cadena de caracteres, entero, lógico, etcétera.). Los campos pueden incluso variar en longitud. En la mayoría de los lenguajes de programación los campos de longitud variable no están soportados y se suponen de longitud fija. Campos Fecha Nombre Dirección Estudios Salario Trienios de nacimiento Figura 9.1. Campos de un registro. Un campo es la unidad mínima de información de un registro. Los datos contenidos en un campo se dividen con frecuencia en subcampos; por ejemplo, el campo fecha se di- vide en los subcampos día, mes, año. Campo 0 7 0 7 1 9 9 5 Subcampo Día Mes Año Los rangos numéricos de variación de los subcampos anteriores son: 1 ≤ día ≤ 31 1 ≤ mes ≤ 12 1 ≤ año ≤ 1987 9.1.2. Registros Un registro es una colección de información, normalmente relativa a una entidad particular. Un registro es una co- lecció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 determinado empleado que contiene los campos de nombre, dirección, fecha de nacimiento, estudios, salario, trienios, etc. Los registros pueden ser todos de longitud fija; por ejemplo, los registros de empleados pueden contener el mis- mo número de campos, cada uno de la misma longitud para nombre, dirección, fecha, etc. También pueden ser de longitud variables. 310 Fundamentos de programación Los registros organizados en campos se denominan registros lógicos. Registro de datos N N = longitud del registro Figura 9.2. Registro. Nota El concepto de registro es similar al concepto de estructura (struct) estudiado en el Capítulo 7, ya que ambas estructuras de datos permiten almacenar datos de tipo heterogéneo. 9.1.3. Archivos (ficheros) Un fichero (archivo) de datos —o simplemente un archivo— es una colección de registros relacionados entre sí con aspectos en común y organizados para un propósito específico. Por ejemplo, un fichero de una clase escolar contiene un conjunto de registros de los estudiantes de esa clase. Otros ejemplos pueden ser el fichero de nóminas de una empresa, inventarios, stocks, etc. La Figura 9.3 recoge la estructura de un archivo correspondiente a los suscriptores de una revista de informá- tica. Registro 4 Registro 3 Registro 2 Registro 1 Nombre Profesión Dirección Teléfono Ciudad Figura 9.3. Estructuras de un archivo “suscriptores”. Un archivo en una computadora es una estructura diseñada para contener datos. Los datos están organizados de tal modo que puedan ser recuperados fácilmente, actualizados o borrados y almacenados de nuevo en el archivo con todos los campos realizados. 9.1.4. Bases de datos Una colección de archivos a los que puede accederse por un conjunto de programas y que contienen todos ellos da- tos relacionados constituye una base de datos. Así, una base de datos de una universidad puede contener archivos de estudiantes, archivos de nóminas, inventarios de equipos, etc. 9.1.5. Estructura jerárquica Los conceptos carácter, campos, registro, archivo y base de datos son conceptos lógicos que se refieren al medio en que el usuario de computadoras ve los datos y se organizan. Las estructuras de datos se organizan de un modo jerár- quico, de modo que el nivel más alto lo constituye la base de datos y el nivel más bajo el carácter. Archivos (ﬁcheros) 311 9.1.6. Jerarquía de datos Una computadora, como ya conoce el lector (Capítulo 1), procesa todos los datos como combinaciones de ceros y unos. Tal elemento de los datos se denomina bit (binary digit). Sin embargo, como se puede deducir fácilmente, es difícil para los programadores trabajar con datos en estos formatos de bits de bajo nivel. En su lugar, los programa- dores prefieren trabajar con caracteres tales como los dígitos decimales (0-9), letras (A-Z y a-z) o símbolos espe- ciales (&, *, , @, €, #,...). El conjunto de todos los caracteres utilizados para escribir los programas se denomina conjunto o juegos de caracteres de la computadora. Cada carácter se representa como un patrón de ceros y unos. Por ejemplo, en Java, los caracteres son caracteres Unicode (Capítulo 1) compuestos de 2 bytes. Al igual que los caracteres se componen de bits, los campos se componen de caracteres o bytes. Un campo es un grupo de caracteres o bytes que representan un significado. Por ejemplo, un campo puede constar de letras ma- yúsculas y minúsculas que representan el nombre de una ciudad. Los datos procesados por las computadoras se organizan en jerarquías de datos formando estructuras a partir de bits, caracteres, campos, etc. Los campos (variables de instancias en C++ y Java) se agrupan en registros que se implementan en una clase en Java o en C++. Un registro es un grupo de campos relacionados que se implementan con tipos de datos básicos o estructurados. En un sistema de matrícula en una universidad, un registro de un alumno o de un profesor puede cons- tar de los siguientes campos: Nombre (cadena). Número de expediente (entero). Número de Documento Nacional de Identidad o Pasaporte (entero doble). Año de nacimiento (entero). Estudios (cadena). Un archivo es un grupo de registros relacionados. Así, una universidad puede tener muchos alumnos y profesores, y un archivo de alumnos contiene un registro para cada empleado. Un archivo de una universidad puede contener miles de registros y millones o incluso miles de millones de caracteres de información. Las Figura 9.4 muestra la jerarquía de datos de un archivo (byte, campo, registro, archivo). Base de datos Archivos Registros Campos Subcampos Caracteres Figura 9.4. Estructuras jerárquicas de datos. Los registros poseen una clave o llave que identifica a cada registro y que es única para diferenciarla de otros registros. En registros de nombres es usual que el campo clave sea el pasaporte o el DNI (Documento Nacional de Identidad). Un conjunto de archivos relacionados se denomina base de datos. En los negocios o en la administración, los datos se almacenan en bases de datos y en muchos archivos diferentes. Por ejemplo, las universidades pueden tener archivos de profesores, archivos de estudiantes, archivos de planes de estudio, archivos de nóminas de profesores y de PAS (Personal de Administración y Servicios). Otra jerarquía de datos son los sistemas de gestión de bases de datos (SGBD o DBMS) que es un conjunto de programas diseñados para crear y administrar bases de datos. 312 Fundamentos de programación 9.2. CONCEPTOS Y DEFINICIONES = TERMINOLOGÍA Aunque en el apartado anterior ya se han comentado algunos términos relativos a la teoría de archivos, en este apar- tado se enunciarán todos los términos más utilizados en la gestión y diseño de archivos. 9.2.1. Clave (indicativo) Una clave (key) o indicativo es un campo de datos que identifica el registro y lo diferencia de otros registros. Esta clave debe ser diferente para cada registro. Claves típicas son nombres o números de identificación. 9.2.2. Registro físico o bloque Un registro físico o bloque es la cantidad más pequeña de datos que pueden transferirse en una operación de entra- da/salida entre la memoria central y los dispositivos periféricos o viceversa. Ejemplos de registros físicos son: una tarjeta perforada, una línea de impresión, un sector de un disco magnético, etc. Un bloque puede contener uno o más registros lógicos. Un registro lógico puede ocupar menos de un registro físico, un registro físico o más de un registro físico. 9.2.3. Factor de bloqueo Otra característica que es importante en relación con los archivos es el concepto de factor de bloqueo o blocaje. El número de registros lógicos que puede contener un registro físico se denomina factor de bloqueo. Se pueden dar las siguientes situaciones: Registro lógico > Registro físico. En un bloque se contienen varios registros físicos por bloque; se denominan registros expandidos. Registro lógico = Registro físico. El factor de bloqueo es 1 y se dice que los registros no están bloqueados. Registro lógico < Registro físico. El factor de bloqueo es mayor que 1 y los registros están bloqueados. Registro Espacio entre bloques Bloque a) Un registro por bloque (factor = 1) Registro1 Registro2 Registro3 Registro4 Espacio entre bloques Bloque b) N registros por bloque (factor = N) Figura 9.5. Factor de bloqueo. La importancia del factor de bloqueo se puede apreciar mejor con un ejemplo. Supongamos que se tienen dos archivos. Uno de ellos tiene un factor de bloqueo de 1 (un registro en cada bloque). El otro archivo tiene un factor de bloqueo de 10 (10 registros/bloque). Si cada archivo contiene un millón de registros, el segundo archivo requeri- rá 900.000 operaciones de entrada/salida menos para leer todos los registros. En el caso de las computadoras perso- nales con un tiempo medio de acceso de 90 milisegundos, el primer archivo emplearía alrededor de 24 horas más para leer todos los registros del archivo. Archivos (ﬁcheros) 313 Un factor de bloqueo mayor que 1 siempre mejora el rendimiento; entonces, ¿por qué no incluir todos los regis- tros en un solo bloque? La razón reside en que las operaciones de entrada/salida que se realizan por bloques se hacen a través de un área de la memoria central denominada memoria intermedia (buffer) y entonces el aumento del bloque implicará aumento de la memoria intermedia y, por consiguiente, se reducirá el tamaño de la memoria central. El tamaño de una memoria intermedia de un archivo es el mismo que el del tamaño de un bloque. Como la me- moria central es más cara que la memoria secundaria, no conviene aumentar el tamaño del bloque alegremente, sino más bien conseguir un equilibrio entre ambos criterios. En el caso de las computadoras personales, el registro físico puede ser un sector del disco (512 bytes). Memoria central Cinta Programa Flujo de datos Almacenamiento del usuario secundario Disco Memoria intermedia La Tabla 9.1 resume los conceptos lógicos y físicos de un registro. Tabla 9.1. Unidades de datos lógicos y físicos Organización lógica Organización físcia Descripción Bit Un dígito binario. Carácter Byte (octeto, 8 bits) En la mayoría de los códigos un carácter se representa aproximadamente por un byte. Campo Palabra Un campo es un conjunto relacionado de caracteres. Una palabra de computadora es un número fijo de bytes. Registro Bloque (1 página = Los registros pueden estar bloqueados. bloques de longitud) Archivo Área Varios archivos se pueden almacenar en un área de almacenamiento. Base de datos Áreas Colección de archivos de datos relacionados que se pueden organizar en una base de datos. Resumen de archivos Un archivo está siempre almacenado en un soporte externo a la memoria central. Existe independencia de las informaciones respecto de los programas. Todo programa de tratamiento intercambia información con el archivo y la unidad básica de entrada/salida es el registro. La información almacenada es permanente. En un momento dado, los datos extraídos por el archivo son los de un registro y no los del archivo completo. Los archivos en memoria auxiliar permiten una gran capacidad de almacenamiento. 9.3. SOPORTES SECUENCIALES Y DIRECCIONABLES El soporte es el medio físico donde se almacenan los datos. Los tipos de soporte utilizados en la gestión de archi- vos son: Soportes secuenciales. Soportes direccionables. 314 Fundamentos de programación Los soportes secuenciales son aquellos en los que los registros —informaciones— están escritos unos a conti- nuación de otros y para acceder a un determinado registro n se necesita pasar por los n – 1 registros anteriores. Los soportes direccionables se estructuran de modo que las informaciones registradas se pueden localizar direc- tamente por su dirección y no se requiere pasar por los registros precedentes. En estos soportes los registros deben poseer un campo clave que los diferencie del resto de los registros del archivo. Una dirección en un soporte direc- cionable puede ser número de pista y número de sector en un disco. Los soportes direccionables son los discos magnéticos, aunque pueden actuar como soporte secuencial. 9.4. ORGANIZACIÓN DE ARCHIVOS Según las características del soporte empleado y el modo en que se han organizado los registros, se consideran dos tipos de acceso a los registros de un archivo: Acceso secuencial. Acceso directo. El acceso secuencial implica el acceso a un archivo según el orden de almacenamiento de sus registros, uno tras otro. El acceso directo implica el acceso a un registro determinado, sin que ello implique la consulta de los registros precedentes. Este tipo de acceso sólo es posible con soportes direccionables. La organización de un archivo define la forma en la que los registros se disponen sobre el soporte de almacena- miento, o también se define la organización como la forma en que se estructuran los datos en un archivo. En general, se consideran tres organizaciones fundamentales: Organización secuencial. Organización directa o aleatoria (“random”). Organización secuencial indexada (“indexed”). 9.4.1. Organización secuencial Un archivo con organización secuencial es una sucesión de registros almacenados consecutivamente sobre el sopor- te externo, de tal modo que para acceder a un registro n dado es obligatorio pasar por todos los n – 1 artículos que le preceden. Los registros se graban consecutivamente cuando el archivo se crea y se debe acceder consecutivamente cuando se leen dichos registros. Principio del archivo Registro 1 Registro 2.... Registro I – 1 Registro I Registro I + 1.... Registro N – 1 Fin del archivo Registro N Figura 9.6. Organización secuencial. Archivos (ﬁcheros) 315 El orden físico en que fueron grabados (escritos) los registros es el orden de lectura de los mismos. Todos los tipos de dispositivos de memoria auxiliar soportan la organización secuencial. Los archivos organizados secuencialmente contienen un registro particular —el último— que contiene una marca fin de archivo (EOF o bien FF). Esta marca fin de archivo puede ser un carácter especial como '*'. 9.4.2. Organización directa Un archivo está organizado en modo directo cuando el orden físico no se corresponde con el orden lógico. Los da- tos se sitúan en el archivo y se accede a ellos directamente mediante su posición, es decir, el lugar relativo que ocupan. Esta organización tiene la ventaja de que se pueden leer y escribir registros en cualquier orden y posición. Son muy rápidos de acceso a la información que contienen. La organización directa tiene el inconveniente de que necesita programar la relación existente entre el contenido de un registro y la posición que ocupa. El acceso a los registros en modo directo implica la posible existencia de huecos libres dentro del soporte y, por consecuencia, pueden existir huecos libres entre registros. La correspondencia entre clave y dirección debe poder ser programada y la determinación de la relación entre el registro y su posición física se obtiene mediante una fórmula. Las condiciones para que un archivo sea de organización directa son: Almacenado en un soporte direccionable. Los registros deben contener un campo específico denominado clave que identifica cada registro de modo úni- co, es decir, dos registros distintos no pueden tener un mismo valor de clave. Existencia de una correspondencia entre los posibles valores de la clave y las direcciones disponibles sobre el soporte. Un soporte direccionable es normalmente un disco o paquete de discos. Cada posición se localiza por su dirección absoluta, que en el caso del disco suele venir definida por dos parámetros —número de pista y número de sector— o bien por tres parámetros —pista, sector y número de cilindro—; un cilindro i es el conjunto de pistas de número i de cada superficie de almacenamiento de la pila. En la práctica el programador no gestiona directamente direcciones absolutas, sino direcciones relativas respecto al principio del archivo. La manipulación de direcciones relativas permite diseñar el programa con independencia de la posición absoluta del archivo en el soporte. El programador crea una relación perfectamente definida entre la clave indicativa de cada registro y su posición física dentro del dispositivo de almacenamiento. Esta relación, en ocasiones, produce colisiones. Consideremos a continuación el fenómeno de las colisiones mediante un ejemplo. La clave de los registros de estudiantes de una Facultad de Ciencias es el número de expediente escolar que se le asigna en el momento de la matriculación y que consta de ocho dígitos. Si el número de estudiantes es un número decimal de ocho dígitos, existen 108 posibles números de estudiantes (0 a 99999999), aunque lógicamente nunca existirán tantos estudiantes (incluso incluyendo alumnos ya graduados). El archivo de estudiantes constará a lo sumo de decenas o centenas de miles de estudiantes. Se desea almacenar este archivo en un disco sin utilizar mucho espa- cio. Si se desea obtener el algoritmo de direccionamiento, se necesita una función de conversión de claves o función “hash”. Suponiendo que N es el número de posiciones disponibles para el archivo, el algoritmo de direccionamien- to convierte cada valor de la clave en una dirección relativa d, comprendida entre 1 y N. Como la clave puede ser numérica o alfanumérica, el algoritmo de conversión debe prever esta posibilidad y asignar a cada registro corres- pondiente a una clave una posición física en el soporte de almacenamiento. Así mismo, el algoritmo o función de conversión de claves debe eliminar o reducir al máximo las colisiones. Se dice que en un algoritmo de conversión de claves se produce una colisión cuando dos registros de claves distintas producen la misma dirección física en el so- porte. El inconveniente de una colisión radica en el hecho de tener que situar el registro en una posición diferente de la indicada por el algoritmo de conversión y, por consiguiente, el acceso a este registro será más lento. Las colisiones son difíciles de evitar en las organizaciones directas. Sin embargo, un tratamiento adecuado en las operaciones de lectura/escritura disminuirá su efecto perjudicial en el archivo. Para representar la función de transformación o conversión de claves (hash), se puede utilizar una notación matemática. Así, si K es una clave, f(K) es la correspondiente dirección; f es la función llamada función de con- versión. 316 Fundamentos de programación EJEMPLO 9.1 Una compañía de empleados tiene un número determinado de vendedores y un archivo en el que cada registro co- rresponde a un vendedor. Existen 200 vendedores, cada uno referenciado por un número de cinco dígitos. Si tuvié- semos que asignar un archivo de 100.000 registros, cada registro se corresponderá con una posición del disco. Para el diseño del archivo crearemos 250 registros (un 25 por 100 más que el número de registros necesarios —25 por 100 suele ser un porcentaje habitual—) que se distribuirán de la siguiente forma: 1. Posiciones 0-199 constituyen el área principal del archivo y en ella se almacenarán todos los vendedores. 2. Posiciones 200-249 constituyen el área de desbordamiento, si K(1) K(2), pero f(K(1)) = f(K(2)), y el re- gistro con clave K(1) ya está almacenado en el área principal, entonces el registro con K(2) se almacena en el área de desbordamiento. La función f se puede definir como: f(k) = resto cuando K se divide por 199, esto es, el módulo de 199; 199 ha sido elegido por ser el número primo mayor y que es menor que el tamaño del área principal. Para establecer el archivo se borran primero 250 posiciones. A continuación, para cada registro de vendedor se calcula p = f(K). Si la posición p está vacía, se almacena el registro en ella. En caso contrario se busca secuencial- mente a través de las posiciones 200, 201,..., para el registro con la clave deseada. 9.4.3. Organización secuencial indexada Un diccionario es un archivo secuencial, cuyos registros son las entradas y cuyas claves son las palabras definidas por las entradas. Para buscar una palabra (una clave) no se busca secuencialmente desde la “a” hasta la “z”, sino que se abre el diccionario por la letra inicial de la palabra. Si se desea buscar “índice”, se abre el índice por la letra I y en su primera página se busca la cabecera de página hasta encontrar la página más próxima a la palabra, buscando a continuación palabra a palabra hasta encontrar “índice”. El diccionario es un ejemplo típico de archivo secuencial indexado con dos niveles de índices, el nivel superior para las letras iniciales y el nivel menor para las cabeceras de página. En una organización de computadora las letras y las cabeceras de páginas se guardarán en un archivo de ín- dice independiente de las entradas del diccionario (archivo de datos). Por consiguiente, cada archivo secuencial in- dexado consta de un archivo índice y un archivo de datos. Un archivo está organizado en forma secuencial indexada si: El tipo de sus registros contiene un campo clave identificador. Los registros están situados en un soporte direccionable por el orden de los valores indicados por la clave. Un índice para cada posición direccionable, la dirección de la posición y el valor de la clave; en esencia, el índice contiene la clave del último registro y la dirección de acceso al primer registro del bloque. Un archivo en organización secuencial indexada consta de las siguientes partes: Área de datos o primaria: contiene los registros en forma secuencial y está organizada en secuencia de claves sin dejar huecos intercalados. Área de índices: es una tabla que contiene los niveles de índice, la existencia de varios índices enlazados se denomina nivel de indexación. Área de desbordamiento o excedentes: utilizada, si fuese necesario, para las actualizaciones. El área de índices es equivalente, en su función, al índice de un libro. En ella se refleja el valor de la clave iden- tificativa más alta de cada grupo de registros del archivo y la dirección de almacenamiento del grupo. Los archivos secuenciales indexados presentan las siguientes ventajas: Rápido acceso. El sistema de gestión de archivos se encarga de relacionar la posición de cada registro con su contenido median- te la tabla de índices. Archivos (ﬁcheros) 317 CLAVE DIRECCIÓN CLAVE DATOS Área de Área 010 15 15 010 índices principal 011 24 020 012. 36 030.. 54 040 019.. 020 24.. 021... 240 090.. 029 030 36 031... 039 040 54 041... 049 050... 090 240 091... 100 0 Figura 9.7. Organización secuencial indexada. Y los siguientes inconvenientes: Desaprovechamiento del espacio por quedar huecos intermedios cada vez que se actualiza el archivo. Se necesita espacio adicional para el área de índices. Los soportes que se utilizan para esta organización son los que permiten el acceso directo —los discos magnéti- cos—. Los soportes de acceso secuencial no pueden utilizarse, ya que no disponen de direcciones para las posiciones de almacenamiento. 9.5. OPERACIONES SOBRE ARCHIVOS Tras la decisión del tipo de organización que ha de tener el archivo y los métodos de acceso que se van a aplicar para su manipulación, es preciso considerar todas las posibles operaciones que conciernen a los registros de un archivo. Las distintas operaciones que se pueden realizar son: Creación. Consulta. Actualización (altas, bajas, modificación, consulta). 318 Fundamentos de programación Clasificación. Reorganización. Destrucción (borrado). Reunión, fusión. Rotura, estallido. 9.5.1. Creación de un archivo Es la primera operación que sufrirá el archivo de datos. Implica la elección de un entorno descriptivo que permita un ágil, rápido y eficaz tratamiento del archivo. Para utilizar un archivo, éste tiene que existir, es decir, las informaciones de este archivo tienen que haber sido almacenadas sobre un soporte y ser utilizables. La creación exige organización, estructura, localización o reserva de espacio en el soporte de almacenamiento, transferencia del archivo del soporte antiguo al nuevo. Un archivo puede ser creado por primera vez en un soporte, proceder de otro previamente existente en el mismo o diferente soporte, ser el resultado de un cálculo o ambas cosas a la vez. La Figura 9.8 muestra un organigrama de la creación de un archivo ordenado de empleados de una empresa por el campo clave (número o código de empleado). CREACIÓN MAESTRO DATOS de un archivo (desordenado) en disco Operación de clasificación Número de por número empleado empleado Maestro ordenado Figura 9.8. Creación de un archivo ordenado de empleados. 9.5.2. Consulta de un archivo Es la operación que permite al usuario acceder al archivo de datos para conocer el contenido de uno, varios o todos los registros. Proceso de consulta Figura 9.9. Consulta de un archivo. Archivos (ﬁcheros) 319 9.5.3. Actualización de un archivo Es la operación que permite tener actualizado (puesto al día) el archivo, de tal modo que sea posible realizar las si- guientes operaciones con sus registros: Consulta del contenido de un registro. Inserción de un registro nuevo en el archivo. Supresión de un registro existente. Modificación de un registro. Un ejemplo de actualización es el de un archivo de un almacén, cuyos registros contienen las existencias de cada artículo, precios, proveedores, etc. Las existencias, precios, etc., varían continuamente y exigen una actualización simultánea del archivo con cada operación de consulta. Proceso de actualización Figura 9.10. Actualización de un archivo (I). Inserción de un registro Localizar posición de inserción Posición No libre Sí Grabar Transferir áreas nuevo registro de entrada a salida Fin Figura 9.11. Actualización de un archivo (II). 9.5.4. Clasificación de un archivo Una operación muy importante en un archivo es la clasificación u ordenación (sort, en inglés). Esta clasificación se realizará de acuerdo con el valor de un campo específico, pudiendo ser ascendente (creciente) o descendente (decre- ciente): alfabética o numérica (véase Figura 9.12). 320 Fundamentos de programación Clasificación Clasificación Copia Figura 9.12. Clasificación de un archivo. 9.5.5. Reorganización de un archivo Las operaciones sobre archivos modifican la estructura inicial o la óptima de un archivo. Los índices, enlaces (pun- teros), zonas de sinónimos, zonas de desbordamiento, etc., se modifican con el paso del tiempo, lo que hace a la operación de acceso al registro cada vez más lenta. La reorganización suele consistir en la copia de un nuevo archivo a partir del archivo modificado, a fin de obtener una nueva estructura lo más óptima posible. 9.5.6. Destrucción de un archivo Es la operación inversa a la creación de un archivo (kill, en inglés). Cuando se destruye (anula o borra) un archivo, éste ya no se puede utilizar y, por consiguiente, no se podrá acceder a ninguno de sus registros (Figura 9.13). 9.5.7. Reunión, fusión de un archivo Reunión. Esta operación permite obtener un archivo a partir de otros varios (Figura 9.14). Fusión. Se realiza una fusión cuando se reúnen varios archivos en uno solo, intercalándose unos en otros, siguien- do unos criterios determinados. Proceso de reorganización Reunión/ fusión Figura 9.13. Reorganización de un archivo. Figura 9.14. Fusión de archivos. Archivos (ﬁcheros) 321 9.5.8. Rotura/estallido de un archivo Es la operación de obtener varios archivos a partir de un mismo archivo inicial. Rotura Figura 9.15. Rotura de un archivo. 9.6. GESTIÓN DE ARCHIVOS Las operaciones sobre archivos se realizan mediante programas y el primer paso para poder gestionar un archivo mediante un programa es declarar un identificador lógico que se asocie al nombre externo del archivo para permitir su manipulación. La declaración se realizará con una serie de instrucciones como las que se muestran a continuación, cuya asociación permite establecer la organización del archivo y estructura de sus registros lógicos. tipo registro: :.... fin_registro archivo_ de :>) para los tipos primitivos. Este operador convierte los datos a una secuencia de caracteres y los inserta en el flujo. Los flujos cin y cout se declaran en el lenguaje por usted, pero si desea que un flujo se conecte a un archivo, se debe declarar justo antes de que se pueda declarar cualquier otra variable. 9.7.3. Flujos en Java El procedimiento para utilizar bien un flujo de bytes o un flujo de caracteres en Java es, en gran medida, el mismo. Antes de comenzar a trabajar con las clases específicas de la biblioteca de clases java.io, es útil revisar el proceso de crear y utilizar flujos. Para un flujo de entrada, el primer paso es crear un objeto asociado con la fuente de datos. Por ejemplo, si la fuente es un archivo de su unidad de disco duro, un objeto FileInputStream se puede asociar con este archivo. Después que se tiene un objeto de flujo, se puede leer la información desde el flujo utilizando uno de los métodos del objeto FileInputStream incluye un método read que devuelve un byte leído desde el teclado. Cuando se termina de leer la información del flujo se llama al método close( ) para indicar que se ha termi- nado de utilizar el flujo. En el caso de un flujo de salida, se crea un objeto asociado con el destino de los datos. Tal objeto se puede crear de la clase BufferedWriter que representa un medio eficiente de crear archivos de texto. 326 Fundamentos de programación El método write( ) es el medio más simple para enviar información al destino del flujo de salida. Al igual que con los flujos de entrada, el método close( ) se llama en un flujo de salida cuando no se tiene más información que enviar. 9.7.4. Consideraciones prácticas en Java y C# Java y C# realizan las operaciones en archivos a través de flujos, manipulados por clases, que conectan con el me- dio de almacenamiento. De esta forma, para crear y abrir un archivo, se requiere utilizar una clase que defina la funcionalidad del flujo. Los flujos determinan el sentido de la comunicación (lectura, escritura, o lectura/escritura), la posibilidad de posicionamiento directo o no en un determinado registro y la forma de leer y/o escribir en el ar- chivo. Cerrar el archivo implica cerrar el flujo. Así la siguiente instrucción en Java crea un flujo que permite la lectura/escritura (rw) en un archivo donde se podrá efectuar posicionamiento directo y cuyo nombre externo es em- pleados.dat. RandomAccessFile e = new RandomAccessFile ("empleados.dat", "rw"); Pueden utilizarse flujos de bytes, caracteres, cadenas o tipos primitivos. Por ejemplo, en Java la clase Fi- leInputStream permite crear un flujo para lectura secuencial de bytes desde un archivo, mientras FileReader lo crea para la lectura secuencial de caracteres y RandomAccessFile, como ya se ha comentado, admite posiciona- miento directo y permite la lectura/escritura de datos tipos primitivos. La personalización de flujos se consigue por asociación o encadenamiento de otros flujos sobre los flujos base de apertura de archivos. Una aplicación práctica de esta propiedad en Java puede ser permitir la lectura de una cade- na de caracteres desde un flujo de entrada BufferedReader f = new BufferedReader (new FileReader("datos.txt")); cadena = f.readLine(); //lee una cadena del archivo f.close(); // cierra el archivo En C# la situación es similar y sobre los flujos base, que conectan al medio de almacenamiento, pueden encade- narse otros para efectuar tratamientos especiales de la información. BinaryWriter f = new BinaryWriter (new FileStream("notas.dat", FileMode.OpenOrCreate, FileAccess.Write)); f.Write (5.34 * 2); f.Close(); // Cerrar el archivo 9.8. MANTENIMIENTO DE ARCHIVOS La operación de mantenimiento de un archivo incluye todas las operaciones que sufre un archivo durante su vida y desde su creación hasta su eliminación o borrado. El mantenimiento de un archivo consta de dos operaciones diferentes: actualización, consulta. La actualización es la operación de eliminar o modificar los datos ya existentes, o bien introducir nuevos datos. En esencia, es la puesta al día de los datos del archivo. Archivos (ﬁcheros) 327 Las operaciones de actualización son: altas, bajas, modificaciones. Las operaciones de consulta tienen como finalidad obtener información total o parcial de los datos almacena- dos en un archivo y presentarlos en dispositivos de salida: pantalla o impresora, bien como resultados o como lis- tados. Todas las operaciones de mantenimiento de archivos suelen constituir módulos independientes del programa prin- cipal y su diseño se realiza con subprogramas (subrutinas o procedimientos específicos). Así, los subprogramas de mantenimiento de un archivo constarán de: Altas Una operación de alta en un archivo consiste en la adición de un nuevo registro. En un archivo de empleados, un alta consistirá en introducir los datos de un nuevo empleado. Para situar correctamente un alta, se deberá conocer la po- sición donde se desea almacenar el registro correspondiente: al principio, en el interior o al final de un archivo. El algoritmo del subprograma ALTAS debe contemplar la comprobación de que el registro a dar de alta no existe previamente. Bajas Una baja es la acción de eliminar un registro de un archivo. La baja de un registro se puede presentar de dos formas distintas: indicación del registro específico que se desea dar de baja o bien visualizar los registros del archivo para que el usuario elija el registro a borrar. La baja de un registro puede ser lógica o física. Una baja lógica supone el no borrado del registro en el archivo. Esta baja lógica se manifiesta en un determinado campo del registro con una bandera, indicador o “flag” —carácter *, $, etc.—, o bien con la escritura o rellenado con espacios en blanco de algún campo en el registro específico. Una baja física implica el borrado y desaparición del registro, de modo que se crea un nuevo archivo que no incluye el registro dado de baja. Modificaciones Una modificación en un archivo consiste en la operación de cambiar total o parcialmente el contenido de uno de sus registros. Esta fase es típica cuando cambia el contenido de un determinado campo de un archivo; por ejemplo, la dirección o la edad de un empleado. La forma práctica de modificar un registro es la visualización del contenido de sus campos; para ello se debe elegir el registro o registros a modificar. El proceso consiste en la lectura del registro, modificación de su contenido y escritura, total o parcial del mismo. Consulta La operación de consulta tiene como fin visualizar la información contenida en el archivo, bien de un modo comple- to —bien de modo parcial—, examen de uno o más registros. Las operaciones de consulta de archivo deben contemplar diversos aspectos que faciliten la posibilidad de con- servación de datos. Los aspectos más interesantes a tener en cuenta son: opción de visualización en pantalla o listado en impresora, detención de la consulta a voluntad del usuario, listado por registros o campos individuales o bien listado total del archivo (en este caso deberá existir la posi- bilidad de impresión de listados, con opciones de saltos de página correctos). 328 Fundamentos de programación 9.8.1. Operaciones sobre registros Las operaciones de transferencia de datos a/desde un dispositivo a la memoria central se realizan mediante las ins- trucciones: leer (, lista de entrada de datos) escribir (, lista de salida de datos) organización directa lista de entrada de datos = numero_registro, nombre_registro lista de salida de datos = numero_registro, nombre_registro organización secuencial lista de entrada de datos = lista de salida de datos = Las operaciones de acceso a un registro y de paso de un registro a otro se realiza con las acciones leer y es- cribir. 9.9. PROCESAMIENTO DE ARCHIVOS SECUENCIALES (ALGORITMOS) En un archivo secuencial los registros se insertan en el archivo en orden cronológico de llegada al soporte, es decir, un registro de datos se almacena inmediatamente a continuación del registro anterior. Los archivos secuenciales terminan con una marca final de archivo (FDA o EOF). Cuando se tengan que añadir registros a un archivo secuencial se añadirán al final, inmediatamente por delante de las marcas fin de archivos. Las operaciones básicas que se permiten en un archivo secuencial son: escribir su contenido, añadir un registro al final del archivo y consultar sus registros. Las demás operaciones exigen una programación específica. Los archivos secuenciales son los que ocupan menos memoria y son útiles cuando se desconoce a priori el tama- ño de los datos y se requieren registros de longitud variable. También son muy empleados para el almacenamiento de información, cuyos contenidos sufran pocas modificaciones en el transcurso de su vida útil. Es característico de los archivos secuenciales el no poder ser utilizados simultáneamente para lectura y escri- tura. 9.9.1. Creación La creación de un archivo secuencial es un proceso secuencial, ya que los registros se almacenan consecutivamente en el mismo orden en que se introducen en el archivo. El método de creación de un archivo consiste en la ejecución de un programa adecuado que permita la entrada de datos al archivo desde el terminal. El sistema usual es el interactivo, en el que el programa solicita los datos al usuario que los introduce por teclado, al terminar se introduce una marca final de archivo, que supone el final físico del archivo. En los archivos secuenciales, EOF o FDA es una función lógica que toma el valor cierto si se ha alcanzado el final de archivo y falso en caso contrario. La creación del archivo requerirá los siguientes pasos: abrir el archivo, leer datos del registro, grabar registro, cerrar archivo. Archivos (ﬁcheros) 329 El algoritmo de creación es el siguiente: algoritmo crea_sec tipo registro: datos_personales : nombre_campo1 : nombre_campo2........................... fin_registro archivo_s de datos_personales: arch var arch :f datos_personales :persona inicio crear (f,) abrir (f,e,) leer_reg (persona) { utilizamos un procedimiento para no tener que detallar la lectura} mientras no ultimo_dato(persona) hacer escribir_f_reg (f,persona) //la escritura se realizará campo a campo leer_reg(persona) fin_mientras cerrar(f) fin Se considera que se permite la lectura y escritura en el archivo de los datos tal y como se almacenan en memoria. Un archivo de texto es un archivo secuencial en el que sólo se leen y escriben series de caracteres y no sería nece- sario especificar en la declaración del archivo el tipo de registros que lo constituyen, pues siempre son líneas. 9.9.2. Consulta El proceso de búsqueda o consulta de una información en un archivo de organización secuencial se debe efectuar obligatoriamente en modo secuencial. Por ejemplo, si se desea consultar la información contenida en el registro 50, se deberán leer previamente los 49 primeros registros que le preceden en orden secuencial. En el caso de un archivo de personal, si se desea buscar un registro determinado correspondiente a un determinado empleado, será necesario recorrer —leer— todo el archivo desde el principio hasta encontrar el registro que se busca o la marca final de ar- chivos. Así, para el caso de un archivo de n registros, el número de lecturas de registros efectuadas son: mínimo 1, si el registro buscado es el primero del archivo, máximo n, si el registro buscado es el último o no existe dentro del archivo. Por término medio, el número de lecturas necesarias para encontrar un determinado registro es: n+1 —-— 2 El tiempo de acceso será influyente en las operaciones de lectura/escritura. Así, en el caso de una lista o vector de n elementos almacenados en memoria central puede suponer tiempos de microsegundos o nanosegundos; sin em- bargo, en el caso de un archivo de n registros los tiempos de acceso son de milisegundos o fracciones/múltiples de segundos, lo que supone un tiempo de acceso de 1.000 a 100.000 veces más grande una búsqueda de información en un soporte externo que en memoria central. 330 Fundamentos de programación El algoritmo de consulta de un archivo requerirá un diseño previo de la presentación de la estructura de registros en el dispositivo de salida, de acuerdo al número y longitud de los campos. algoritmo consulta_sec tipo registro: datos_personales : nombre_campo1 : nombre_campo2............:............. fin_registro archivo_s de datos_personales: arch var arch: f datos_personales: persona inicio abrir(f,l,) mientras no fda(f)hacer leer_f_reg(f,persona) fin_mientras cerrar(f) fin o bien: inicio abrir(f,l,) leer_f_reg(f, persona) mientras no fda(f) hacer escribir_reg(persona) leer_f_reg(f,persona) fin_mientras cerrar(f) fin El uso de uno u otro algoritmo depende de cómo el lenguaje de programación detecta la marca de fin de archivo. En la mayor parte de los casos el algoritmo válido es el primero, pues la marca se detecta automáticamente con la lectura del último registro. En el caso de búsqueda de un determinado registro, con un campo clave x, el algoritmo de búsqueda se puede modificar en la siguiente forma con Consulta de un registro Si el archivo no está ordenado: algoritmo consultal_sec tipo registro: datos_personales :nombre_campo1 :nombre_campo2........... :............ fin_registro archivo_s de datos_personales: arch var arch :f datos_personales:persona Archivos (ﬁcheros) 331 :clavebus lógico :encontrado inicio abrir(f,l,) encontrado ← falso leer(clavebus) mientras no encontrado y no fda(f) hacer leer_f_reg(f, persona) si igual(clavebus, persona) entonces encontrado ← verdad fin_si fin_mientras si no encontrado entonces escribir ('No existe') si_no escribir_reg(persona) fin_si cerrar(f) fin Si el archivo está indexado en orden creciente por el campo por el cual realizamos la búsqueda se podría acelerar el proceso, de forma que no sea necesario recorrer todo el fichero para averiguar que un determinado registro no está: algoritmo consulta2_sec tipo registro: datos_personales : nombre_campo1 : nombre_campo2............:............. fin_registro archivo_s de datos_personales: arch var arch : f datos_personales: persona : clavebus lógico : encontrado, pasado inicio abrir(f,l,) encontrado ← falso pasado ← falso leer(clavebus) mientras no encontrado y no pasado y no fda(f) hacer leer_f_reg(f, persona) si igual(clavebus, persona) entonces encontrado ← verdad si_no si menor(clavebus, persona) entonces pasado ← verdad fin_si fin_si fin_mientras si no encontrado entonces escribir ('No existe') 332 Fundamentos de programación si_no escribir_reg(persona) fin_si cerrar(f) fin 9.9.3. Actualización La actualización de un archivo supone: añadir nuevos registros (altas), modificar registros ya existentes (modificaciones), borrar registros (bajas). Altas La operación de dar de alta un determinado registro es similar a la operación de añadir datos a un archivo. algoritmo añade_sec tipo registro: datos_personales : nombre_campo1 : nombre_campo2...........:............. fin_registro archivo_s de datos_personales:arch var arch : f datos_personales: persona inicio abrir(f, e,) leer_reg(persona) mientras no ultimo_dato(persona) hacer escribir_f_reg (f,persona) leer_reg (persona) fin_mientras cerrar fin Bajas Existen dos métodos para dar de baja un registro: 1. Se utiliza un archivo transitorio. 2. Almacenar en un array (vector) todos los registros del archivo, señalando con un indicador o bandera (flag) el registro que se desea dar de baja. Método 1 Se crea un segundo archivo auxiliar, también secuencial, copia del que se trata de actualizar. Se lee el archivo com- pleto registro a registro y en función de su lectura se decide si el registro se debe dar de baja o no. Si el registro se va a dar de baja, se omite la escritura en el archivo auxiliar o transitorio. Si el registro no se va a dar de baja, este registro se escribe en el archivo auxiliar. Archivos (ﬁcheros) 333 Tras terminar la lectura del archivo original, se tendrán dos archivos: original (o maestro) y auxiliar. Archivo Actualización Archivo original auxiliar El proceso de bajas del archivo concluye cambiando el nombre del archivo auxiliar por el de maestro y borrando previamente el archivo maestro original. algoritmo bajas_s tipo registro: datos_personales : nombre_campo1 : nombre_campo2............:.............. fin_registro archivo_s de datos_peersonales:arch var arch :f, faux datos_personales: persona, personaaux lógico :encontrado inicio abrir(f,l, 'antiguo') crear(faux, 'nuevo') abrir(faux, e, 'nuevo') leer(personaaux.nombre_campo1) encontrado ← falso mientras no fda (f) hacer leer_f_reg (f, persona) si personaaux.nombre_campo1 = persona.nombre_campo1 entonces encontrado ← verdad si_no escribir_f_reg (faux, persona) fin_si fin_mientras si no encontrado entonces escribir ('no esta') fin_si cerrar (f, faux) borrar ('antiguo') renombrar ('nuevo', 'antiguo') fin Método 2 Este procedimiento consiste en señalar los registros que se desean dar de baja con un indicador o bandera; estos re- gistros no se graban en el nuevo archivo secuencial que se crea sin los registros dados de baja. Modificaciones El proceso de modificación de un registro consiste en localizar este registro, efectuar dicha modificación y a conti- nuación reescribir el nuevo registro en el archivo. El proceso es similar al de bajas: 334 Fundamentos de programación algoritmo modificacion_sec tipo registro: datos_personales : nombre_campo1 : nombre_campo2............:............. fin archivo_s de datos_personales: arch var arch : f, faux datos_personales: persona, personaaux lógico : encontrado inicio abrir(f, l, 'antiguo') crear(faux, 'nuevo') abrir(faux, e, 'nuevo') leer(personaaux.nombre_campo1) encontrado ← falso mientras_no fda(f) hacer leer_f_reg (f, persona) si personaaux.nombre_campo1=persona.nombre_campo1 entonces encontrado ← verdad modificar (persona) fin_si escribir_f_reg (faux, persona) fin_mientras si no encontrado entonces escribir ('no esta') fin_si cerrar(f, faux) borrar('antiguo') renombrar ('nuevo', 'antiguo') fin El subprograma de modificación de su registro consta de unas pocas instrucciones en las que se debe introducir por teclado el registro completo con indicación de todos sus campos o, por el contrario, el campo o campos que se desea modificar. El subprograma en cuestión podría ser: procedimiento modificar(E/S datos_personales: persona) var carácter: opcion entero : n inicio escribir('R.- registro completo) escribir('C.- campos individuales') escribir('elija opcion:') leer(opcion) según_sea opcion hacer 'R' visualizar(persona) leer_reg(persona) 'C' presentar(persona) solicitar_campo(n) introducir_campo(n, persona) fin_según fin_procedimiento Archivos (ﬁcheros) 335 9.10. PROCESAMIENTO DE ARCHIVOS DIRECTOS (ALGORITMOS) Se dice que un archivo es aleatorio o directo cuando cualquier registro es directamente accesible mediante la especi- ficación de un índice, que da la posición del registro con respecto al origen del fichero. Los archivos aleatorios o directos tienen una gran rapidez para el acceso comparados con los secuenciales; los registros son fáciles de referen- ciar —número de orden del registro—, lo que representa una gran facilidad de mantenimiento. La lectura/escritura de un registro es rápida, ya que se accede directamente al registro y no se necesita recorrer los anteriores. 9.10.1. Operaciones con archivos directos Las operaciones con archivos directos son las usuales, ya vistas anteriormente. Creación El proceso de creación de un archivo directo o aleatorio consiste en ir introduciendo los sucesivos registros en el soporte que los va a contener y en la dirección obtenida, resultante del algoritmo de conversión. Si al introducir un registro se encuentra ocupada la dirección, el nuevo registro deberá ir a la zona de sinónimos o de excedentes. algoritmo crea_dir tipo registro: datos_personales : nombre_campo1........... :............ : nombre_campoN........... :............. fin_registro archivo_d de datos_personales: arch var arch : f datos_personales : persona inicio crear(f,) abrir(f,l/e,).......................... { las operaciones pueden variar con arreglo al modo como pensemos trabajar posteriormente con el archivo (posicionamiento directo en un determinado registro, transformación de clave, indexación) }.......................... cerrar(f) fin En los registros de un archivo directo se suele incluir un campo —ocupado— que pueda servir para distinguir un registro dado de baja o modificado de un alta o de otro que nunca contuvo información. Dentro del proceso de creación del archivo podríamos considerar una inicialización de dicho campo en cada uno de los registros del archivo directo. algoritmo crea_dir const max = tipo registro: datos_personales : cod 336 Fundamentos de programación : ocupado........... :............. : nombre_campon........... :............. fin_registro archivo_d de datos_personales: arch var arch : f datos_personales : persona inicio crear(f,) abrir(f,l/e,) desde i ← 1 hasta Max hacer persona.ocupado ← ' ' escribir(f, i, persona) fin_desde cerrar(f) fin Altas La operación de altas en un archivo directo o aleatorio consiste en ir introduciendo los sucesivos registros en una determinada posición, especificada a través del índice. Mediante el índice nos posicionaremos directamente sobre el byte del fichero que se encuentra en la posición (indice - 1) * tamaño_de() y escribiremos allí nuestro registro. Tratamiento por transformación de clave El método de transformación de clave consiste en transformar un número de orden (clave) en direcciones de alma- cenamiento por medio de un algoritmo de conversión. Cuando las altas se realizan por el método de transformación de clave, la dirección donde introducir un determi- nado registro se conseguirá por la aplicación a la clave del algoritmo de conversión (HASH). Si encontráramos que dicha dirección ya está ocupada, el nuevo registro deberá ir a la zona de sinónimos o de excedentes. algoritmo altas_dir_trcl const findatos = max = tipo registro: datos_personales : cod : ocupado........... :............ : nombre_campon........... :............. fin_registro archivo_d de datos_personales: arch var arch : f datos_personales : persona, personaaux lógico : encontradohueco entero : posi inicio abrir(f,l/e,) leer(personaaux.cod) posi ← HASH(personaaux.cod) Archivos (ﬁcheros) 337 leer(f, posi, persona) si persona.ocupado = '*' entonces encontradohueco ← falso posi ← findatos mientras posi < Max y no encontradohueco hacer posi ← posi + 1 leer(f, posi, persona) si persona.ocupado '*' entonces encontradohueco ← verdad fin_si fin_mientras si_no encontradohueco ← verdad fin_si si encontradohueco entonces leer_otros_campos(personaaux) persona ← personaaux persona.ocupado ← '*' escribir(f, posi, persona) si_no escribir('no está') fin_si cerrar(f) fin Consulta El proceso de consulta de un archivo directo o aleatorio es rápido y debe comenzar con la entrada del índice corres- pondiente al registro que deseamos consultar. El índice permitirá el posicionamiento directo sobre el byte del fichero que se encuentra en la posición (indice - 1) * tamaño_de() algoritmo consultas_dir const max = tipo registro: datos_personales {Cuando el código coincide con el índice o posición del registro en el archivo, no resulta necesario su almacenamiento } : ocupado........... :............ : nombre_campon........... :............. fin_registro archivo_d de datos_personales: arch var arch : f datos_personales : persona lógico : encontrado entero : posi inicio abrir(f,l/e,) leer(posi) 338 Fundamentos de programación si (posi >=1) y (posi >. Las computadoras trabajan con datos binarios. Cuando se leen números de un archivo ASCII, el programa debe procesar los datos carácter a través de una rutina de conversión, lo que entraña grandes recursos. Los archivos binarios, por el contrario, no requieren conversión e inclu- so ocupan menos espacio que los archivos ASCII; su gran inconveniente es que los archivos binarios no se pueden imprimir directamente en una impresora ni visualizar en un terminal. Los archivos ASCII son portables (en la mayoría de los casos) y se pueden mover de una computadora a otra sin grandes problemas. Sin embargo, los archivos binarios son prácticamente no portables; a menos que sea un progra- mador experto es casi imposible hacer portable un archivo binario. 9.12.2. Archivos binarios Los archivos binarios contienen cualquier valor que se puede almacenar en un byte. En estos archivos el final del archivo no se almacena como un byte concreto. Los archivos binarios se escriben copiando una imagen del conteni- do de un segmento de la memoria al disco y por consiguiente los valores numéricos aparecen como unos caracteres extraños que se corresponden con la codificación de dichos valores en la memoria de la computadora, aunque apa- rentemente son prácticamente indescifrables para el programador o el usuario. Cuando se intenta abrir un archivo binario con el editor aparecerán secuencias de caracteres tales como: E#@%Âa^^... ¿Cuál es el archivo más recomendable para utilizar? En la mayoría de los casos, el ASCII es el mejor. Si se tienen pequeñas a medianas cantidades de datos el tiempo de conversión no afecta seriamente a su programa. Por otra parte los archivos ASCII también facilitan la verificación de los datos. Por el contrario, sólo cuando se utilizan grandes cantidades de datos los problemas de espacio y rendimiento, normalmente, aconsejarán utilizar formatos binarios. Los archivos de texto se suelen denominar con la extensión.txt, mientras que los archivos binarios suelen tener la extensión.dat. Los archivos de texto son muy eficientes para intercambiar datos entre aplicaciones y para pro- porcionar datos de entrada de programas que se deban ejecutar varias veces; por el contrario, son poco eficientes para manejar grandes volúmenes de información o bases de datos. Por otra parte, todos los archivos binarios permiten acceso directo, lo cual es muy útil para manejar grandes archivos o bases de datos, ya que se puede ir directamente a leer el registro n sin tener que leer antes el primero, el segundo,…, el n – 1 registros anteriores 9.12.3. Lectura y escritura de archivos Las operaciones típicas sobre un archivo son: creación, lectura y escritura. En el caso de C++ los archivos se mani- pulan mediante un tipo de objeto flujo. Normalmente los objetos que se usan para tratar con archivos se llaman ar- chivos lógicos y archivos físicos son aquellos que almacenan realmente la información en disco (o dispositivos de memoria secundaria correspondiente: disco duro, discos ópticos, memorias flash, etc.). En el caso del lenguaje C++, para todas las operaciones con archivo se necesita utilizar la biblioteca de cabecera fstream.h por lo que es preciso que los programas inserten la sentencia #include o bien en el caso de ANSI C++ estándar #include using namespace std; En general, todo tratamiento de un archivo consta de tres pasos importantes: Apertura del archivo. El modo de implementar la operación dependerá de si un archivo es de lectura o escritura. Acceso al archivo. En esta etapa se llega o imprimen los datos. Cierre del archivo. Actualiza el archivo y se elimina la información no significativa. 346 Fundamentos de programación ACTIVIDADES DE PROGRAMACIÓN RESUELTAS 9.1. Escribir un algoritmo que permita la creación e introducción de los primeros datos en un archivo secuencial, PER- SONAL, que deseamos almacene la información mediante registros de siguiente tipo. tipo registro: datos_personales : nombre_campo1 : nombre_campo2............ :............. fin_registro Análisis del problema Tras la creación y apertura en modo conveniente del archivo, el algoritmo solicitará la introducción de datos por teclado y los almacenará de forma consecutiva en el archivo. Se utilizará una función, ultimo_dato(persona), para determinar el fin en la introducción de datos. Diseño del algoritmo algoritmo Ejercicio_9_1 tipo registro: datos_personales : nombre_campo1 : nombre_campo2............ :............. fin_registro archivo_s de datos_personales: arch var arch : f datos_personales : persona inicio crear (f, 'Personal') abrir (f,e,'Personal') llamar_a leer_reg (persona) // Procedimiento para la lectura de un // registro campo a campo mientras no ultimo_dato(persona) hacer llamar_a escribir_f_reg (f, persona) // Procedimiento auxiliar, no desarrollado, para la // escritura en el archivo del registro campo a campo llamar_a leer_reg(persona) fin_mientras cerrar (f) fin 9.2. Supuesto que deseamos añadir nueva información al archivo PERSONAL, anteriormente creado, diseñar el algoritmo correspondiente. Análisis del problema Al abrir el archivo, para escritura se coloca el puntero de datos al final del mismo, permitiéndonos, con un algoritmo simi- lar al anterior, la adición de nueva información al final del mismo. Diseño del algoritmo algoritmo Ejercicio_9_2 tipo registro: datos_personales : nombre_campo1 Archivos (ﬁcheros) 347 : nombre_campo2............ :............. fin_registro archivo_s de datos_personales: arch var arch : f datos_personales : persona inicio abrir (f,e,'PERSONAL') llamar_a leer_reg (persona) mientras no ultimo_dato (persona) hacer llamar_a escribir_f_reg (f, persona) llamar_a leer_reg (persona) fin_mientras cerrar (f) fin 9.3. Diseñar un algoritmo que muestre por pantalla el contenido de todos los registros del archivo PERSONAL. Análisis del problema Se debe abrir el archivo para lectura y, repetitivamente, leer los registros y mostrarlos por pantalla hasta detectar el fin de fichero. Se considera que la función FDA(id_arch) detecta el final de archivo con la lectura de su último registro. Diseño del algoritmo algoritmo Ejercicio_9_3 tipo registro: datos_personales : nombre_campo1 : nombre_campo2............:............. fin_registro archivo_s de datos_personales: arch var arch : f datos_personales : persona inicio abrir (f,l,'PERSONAL') mientras no fda (f) hacer llamar_a leer_f_reg (f, persona) llamar_a escribir_reg (persona) fin_mientras cerrar (f) fin Si se considera la existencia de un registro especial que marca el fin de archivo, la función FDA(id_arch) se activaría al leer este registro y es necesario modificar algo nuestro algoritmo. inicio abrir (f,l,'PERSONAL') llamar_a leer_f_reg (f, persona) mientras no fda (f) hacer llamar_a escribir_reg (persona) llamar_a leer_f_reg (f, persona) fin_mientras cerrar (f) fin 348 Fundamentos de programación 9.4. Una librería almacena en un archivo secuencial la siguiente información sobre cada uno de sus libros: CODIGO, TI- TULO, AUTOR y PRECIO. El archivo está ordenado ascendentemente por los códigos de los libros —de tipo cadena—, que no pueden re- petirse. Se precisa un algoritmo con las opciones: 1. Insertar: Permitirá insertar nuevos registros en el archivo, que debe mantenerse ordenado en todo mo- mento. 2. Consulta: Buscará registros por el campo CODIGO. Análisis del problema El algoritmo comenzará presentando un menú de opciones a través del cual se haga posible la selección de un procedimien- to u otro. Insertar: Para poder colocar el nuevo registro en el lugar adecuado, sin que se pierda la ordenación inicial, se necesita utilizar un archivo auxiliar. En dicho auxiliar se van copiando los registros hasta llegar al punto donde debe colocarse el nuevo, entonces se escribe y continua con la copia de los restantes registros. Consulta: Como el archivo está ordenado y los códigos no repetidos, el proceso de consulta se puede acelerar. Se recorre el archivo de forma secuencial hasta encontrar el código buscado, o hasta que éste sea menor que el código del registro que se acaba de leer desde el archivo, o bien, si nada de esto ocurre, hasta el fin del archivo. Cuando el código buscado es menor que el código del registro que se acaba de leer desde el archivo, se puede deducir que de ahí en adelante ese registro ya no podrá estar en el fichero, por tanto, se puede abandonar la búsqueda. Diseño del algoritmo algoritmo Ejercicio_9_4 tipo registro : reg cadena : cod cadena : titulo cadena : autor entero : precio fin_registro archivo_s de reg : arch var entero : op inicio repetir escribir( 'MENU') escribir( '1.- INSERTAR') escribir( '2.- CONSULTA') escribir( '3.- FIN') escribir( 'Elija opcion ') leer (op ) según_sea op hacer 1 : llamar_a insertar 2 : llamar_a consulta fin_según hasta_que op = 3 fin procedimiento insertar var arch : f, f2 reg : rf,r Archivos (ﬁcheros) 349 lógico : escrito carácter : resp inicio repetir abrir (f,1,'Libros.dat') crear (f2, 'Nlibros.dat') abrir (f2,e, 'Nlibros.dat') escribir ('Deme el codigo') leer (r.cod) escrito ← falso mientras no FDA(f) hacer llamar_a leer_arch_reg ( f, rf) si rf.cod > r.cod y no escrito entonces // si se lee del archivo un registro con codigo // mayor que el nuevo y este aun no se // ha escrito, es el momento de insertarlo escribir( 'Deme otros campos ') llamar_a completar ( r ) llamar_a escribir_arch_reg ( f2, r ) escrito ← verdad // Se debe marcar que se ha escrito // para que no siga insertandose, desde aqui // en adelante si_no si rf.cod = r.cod entonces escrito ← verdad fin_si fin_si llamar_a escribir_arch_reg ( f2, rf ) // De todas formas se escribe el que // se lee del archivo fin_mientras si no escrito entonces // Si el codigo del nuevo es mayor que todos los del // archivo inicial, se llega al final sin haberlo // escrito escribir ('Deme otros campos') llamar_a completar (r) llamar_a escribir_arch_reg ( f2, r ) fin_si cerrar (f, f2) borrar ( 'Libros.dat') renombrar ('Libros.dat', 'Libros.dat') escribir ('¿Seguir? (s/n) ') leer ( resp ) hasta_que resp = 'n' fin_procedimiento procedimiento consulta var reg: rf, r arch: f carácter: resp lógico: encontrado, pasado inicio resp ← 's' mientras resp 'n' hacer abrir (f, 1, 'Libros.dat') escribir ('Deme el codigo a buscar ') 350 Fundamentos de programación leer ( r.cod) encontrado ← falso pasado ← falso mientras no FDA (f) y no encontrado y no pasado hacer llamar_a leer_arch_reg (f, rf) si r.cod = rf.cod entonces encontrado ← verdad llamar_a escribir_reg ( rf ) si_no si r.cod < rf.cod entonces pasado ← verdad fin_si fin_si fin_mientras si no encontrado entonces escribir ( 'Ese libro no esta') fin_si cerrar (f) escribir ('¿Seguir? (s/n)') leer ( resp ) fin_mientras fin_procedimiento 9.5. Diseñar un algoritmo que efectúe la creación de un archivo directo —PERSONAL—, cuyos registros serán del siguien- te tipo: tipo registro: datos_personales : cod // Campo clave........... :............. : nombre_campoN fin_registro y en el que, posteriormente, vamos a introducir la información empleando el método de transformación de clave. Análisis del problema El método de transformación de claves consiste en introducir los registros, en el soporte que los va a contener, en la direc- ción que proporciona el algoritmo de conversión. Su utilización obliga al almacenamiento del código en el propio registro y hace conveniente la inclusión en el registro de un campo auxiliar —ocupado— en el que se marque si el registro está o no ocupado. Durante el proceso de creación se debe realizar un recorrido de todo el archivo inicializando el campo ocupa- do a vacío, por ejemplo, a espacio. Diseño del algoritmo algoritmo Ejercicio_9_5 const Max = tipo registro: datos_personales : cod // Podria no ser necesario // su almacenamiento, en el caso // de que coincidiera con el // indice............ :............. : nombre_campon fin_registro archivo_d de datos_personales: arch Archivos (ﬁcheros) 351 var arch : f datos personales : persona entero : i inicio crear (f, 'PERSONAL') abrir (f,1/e, 'PERSONAL') desde i ← 1 hasta Max hacer persona.ocupado escribir (f, persona, i) fin_desde cerrar (f) fin 9.6. Se desea introducir información, por el método de transformación de clave, en el archivo PERSONAL creado en el ejercicio anterior, diseñar el algoritmo correspondiente. Análisis del problema Como anteriormente se ha explicado, el método de transformación de claves consiste en introducir los registros, en el so- porte que los va a contener, en la dirección que proporciona el algoritmo de conversión. A veces, registros distintos, sometidos al algoritmo de conversión, proporcionan una misma dirección, por lo que se debe tener previsto un espacio en el disco para el almacenamiento de los registros que han consolidado. Aunque se puede hacer de diferentes maneras, en este caso se reserva espacio para las colisiones en el propio fichero a continuación de la zona de datos. Se supone que la dirección más alta capaz de proporcionar el algoritmo de conversión es Findatos y se colocan las colisiones que se produzcan a partir de allí en posiciones consecutivas del archivo. La inicialización a espacio del campo ocupado se realiza hasta Max, dando por supuesto que Max es mayor que Fin- datos. Diseño del algoritmo algoritmo Ejercicio_9_6 const Findatos = Max = tipo registro: datos_peronales : cod // Podría no ser necesario // su almacenamiento, en el caso // de que coincidiera con el // indice............ :............. : nombre_campon fin_registro archivo_d de datos_personales: arch var arch : f datos personales : persona, personaaux lógico : encontradohueco entero : i inicio abrir (f,1/e, 'PERSONAL') leer (personaaux.cod) posi ← HASH (personaaux.cod) // HASH es el nombre de la funcion de transformacion de // claves. La cual devolvera valores // entre 1 y Findatos, ambos inclusive 352 Fundamentos de programación leer(f, persona, posi) si persona.ocupado ='*' entonces //El '*' indica que esta //ocupado encontradohueco ← falso posi ← Findatos mientras posi < Max y no encontradohueco hacer posi ← posi + 1 leer(f, persona, posi) si persona.ocupado '*' entonces encontradohueco ← verdad fin_si fin_mientras si_no encontradohueco ← verdad fin_si si encontradohueco entonces llamar_a leer_otros_campos (personaaux) persona ← personaaux persona.ocupado ← '*' //Al dar un alta marcaremos //el campo ocupado escribir(f, persona, posi) si_no escribir ('No esta') fin_si cerrar (f) fin CONCEPTOS CLAVE Archivos de texto. Organización directa Registro físico. Concepto de flujo. Organización secuencial. Registro lógico. Organización de archivos. Organización secuencial indexada. RESUMEN Un archivo de datos es un conjunto de datos relacionados que para crear, leer o escribir un archivo se requiere entre sí y almacenados en un dispositivo de almacenamien- utilizar una clase que defina la funcionalidad to externo. Estos datos se encuentran estructurados en una del flujo. Los flujos determinan el sentido de la colección de entidades denominadas artículos o registros, de comunicación (lectura, escritura o lectura/escritura), igual tipo, y que constan a su vez de diferentes entidades de el posicionamiento directo o no en un determinado nivel más bajo denominadas campos. Un archivo de texto registro y la forma de leer y/o escribir en el es el que está formado por líneas, constituidas a su vez por archivo. Pueden utilizarse flujos de bytes cadenas una serie de caracteres, que podrían representar los registros o tipos primitivos. La personalización de flujos se en este tipo de archivos. Por otra parte, los archivos pueden consigue por asociación o encadenamiento de otros ser binarios y almacenar no sólo caracteres sino cualquier flujos con los flujos base de apertura de archivos. tipo de información tal y como se encuentra en memoria. 2. Registro lógico es una colección de información relativa a una entidad particular. El concepto de 1. Java y C# realizan las operaciones en archivos a registro es similar al de estructura desde el punto través de flujos, manipulados por clases, que co- de vista de que permiten almacenar datos de tipo nectan con el medio de almacenamiento. De forma heterogéneo. Archivos (ﬁcheros) 353 3. Registro físico es la cantidad más pequeña de 6. Los archivos de texto se consideran una clase espe- datos que pueden transferirse en una operación de cial de archivos secuenciales. entrada/salida entre la memoria central y los dis- 7. En la organización directa el orden físico de los positivos. registros puede no corresponderse con aquel en el 4. La organización de archivos define la forma en la que han sido introducidos y el acceso a un determi- que los archivos se disponen sobre el soporte de nado registro no obliga a pasar por los que le prece- almacenamiento y puede ser secuencial, directa o den. Para poder acceder a un determinado registro secuencial-indexada. de esta forma se necesita un soporte direccionable 5. La organización secuencial implica que los re- y la longitud de los registros debe ser fija. gistros se almacenan unos al lado de otros en el 8. La organización secuencial-indexada requiere la orden en el que van siendo introducidos y que para existencia de un área de datos, un área de índices, efectuar el acceso a un determinado registro es un área de desbordamiento o colisiones y soporte necesario pasar por los que le preceden. direccionable. EJERCICIOS 9.1. Diseñar un algoritmo que permita crear un archivo campos: número del código del artículo, nivel míni- AGENDA de direcciones cuyos registros constan de los mo, nivel actual, proveedor, precio. siguientes campos: 9.6. El director de un colegio desea realizar un programa NOMBRE que procese un archivo de registros correspondiente DIRECCION a los diferentes alumnos del centro a fin de obtener CIUDAD los siguientes datos: CODIGO POSTAL TELEFONO Nota más alta y número de identificación del alum- EDAD no correspondiente. Nota media por curso. 9.2. Realizar un algoritmo que lea el archivo AGENDA e Nota media del colegio. imprima los registros de toda la agenda. NOTA: Si existen varios alumnos con la misma nota 9.3. Diseñar un algoritmo que copie el archivo secuencial más alta, se deberán visualizar todos ellos. AGENDA de los ejercicios anteriores en un archivo di- recto DIRECTO_AGENDA, de modo que cada registro 9.7. Diseñar un algoritmo que genere un archivo secuen- mantenga su posición relativa. cial BIBLIOTECA, cuyos registros contienen los si- guientes campos: 9.4. Se dispone de un archivo indexado denominado DI- RECTORIO, que contiene los datos de un conjunto de TITULO personas y cuya clave es el número del DNI. Escribir AUTOR un algoritmo capaz de realizar una consulta de un EDITORIAL registro. Si no se encuentra el registro se emite el AÑO DE EDICION correspondiente mensaje de ERROR. ISBN NUMERO DE PAGINAS 9.5. Se dispone de un archivo STOCK correspondiente a la existencia de artículos de un almacén y se desea se- 9.8. Diseñar un algoritmo que permita modificar el con- ñalar aquellos artículos cuyo nivel está por debajo del tenido de alguno de los registros del archivo secuen- mínimo y que visualicen un mensaje “hacer pedido”. cial BIBLIOTECA mediante datos introducidos por Cada artículo contiene un registro con los siguientes teclado.

Fundamentos de Programación (ARCHIVOS) - Joyanes Aguilar - PDF

Document Details

Tags

Related

Summary

Full Transcript