tema 16. ficheros secuenciales igiga.cps.unizar.es/~diegog/ficheros/teaching/fich1.pdf · diego...

1Diego Gutiérrez

Tema 16. Ficheros secuenciales I

2Diego Gutiérrez

Ficheros secuenciales

Índice:

3Diego Gutiérrez

Y si cada vez que apagáramos el ordenador…

…toda la información desapareciera?

4Diego Gutiérrez

Contar el número de vocales de una frase acabada en ‘.’

Contar el número de vocales de El Quijote

Introduzca una frase:Esta es la frase que introduzco.

El número de vocales es de 12

Introduzca El Quijote:

5Diego Gutiérrez

Almacenamiento permanente de la informaciónMemoria RAM: memoria volátilMemoria secundaria: permanente

Ficheros!Físicos (S.O.)Lógicos (variables de un programa)

No es del todo nuevo: input, output

6Diego Gutiérrez

Ficheros secuenciales

Un fichero es un conjunto de unidades de información (componentes o registros) del mismo tipo, almacenado sobre un determinado soporte físico de almacenamiento permanente de la información, con una determinada organización lógica

Acceso secuencial, directo, indexado…

Acceso a los componentes en el orden en que están almacenados: empezando por el primer elemento y accediendo uno a uno a todos los componentes que lo preceden

7Diego Gutiérrez

Ficheros secuenciales

Un fichero secuencial de datos de tipo tpDato es una estructura de datos capaz de almacenar secuencias finitas de datos de tipo tpDato

Ficheros (secuenciales) de texto: la información se almacena en forma de caracteres externos

Ficheros (secuenciales) binarios: la información se almacena con representación binaria interna

tipo tpFichero = fichero de tpDato;

8Diego Gutiérrez

características fundamentalesacceso secuencial a las componentes

dos modos de trabajo: creación e inspección

almacenamiento externo (normalmente en memoria secundaria)

Ambos modos son incompatibles

9Diego Gutiérrez

Tratamiento de secuencias

Concepto de secuenciaUna secuencia tiene asociadas las operaciones:

primero(s): devuelve el dato d1, primer elemento de la secuencia sresto(s): devuelve la secuencia <d2,d3,…,dn> resultado de eliminar el primer elemento de la secuencia s

Para toda secuencia s no vacía se verifica la siguiente relación:s = <primero(s)> • resto(s)

Conviene observar que primero(s) es un dato de tipo T0, mientras que s, <primero(s)> y resto(s) son secuencias de datos de tipo T0.

10Diego Gutiérrez

Tratamiento de secuencias

Concepto de secuencia

s = “Secuencia de ejemplo.”primero(s) = “Secuencia de ejemplo.”resto(s) = “ecuencia de ejemplo.”primero(s) = “ecuencia de ejemplo.”resto(s) = “cuencia de ejemplo.”

Secuencia de ejemplo.

pd

primero(s)

11Diego Gutiérrez

Tratamiento de secuencias

Concepto de secuencia

s = “Secuencia de ejemplo.”primero(s) = “Secuencia de ejemplo.”resto(s) = “ecuencia de ejemplo.”primero(s) = “ecuencia de ejemplo.”resto(s) = “cuencia de ejemplo.”

Secuencia de ejemplo.

pd

primero(s)

pi

12Diego Gutiérrez

Tratamiento de secuencias

Concepto de secuencia

s = “Secuencia de ejemplo.”primero(s) = “Secuencia de ejemplo.”resto(s) = “ecuencia de ejemplo.”primero(s) = “ecuencia de ejemplo.”resto(s) = “cuencia de ejemplo.”

Secuencia de ejemplo.

pd

primero(s)

piDesde esta perspectiva, siempreel primer elemento de la parte derechade la secuencia

13Diego Gutiérrez

Hasta ahora, a cualquier variable se le podía modificar su valor mediante una operación de asignación… Sin embargo, a las variables de tipo fichero no se les puede asignar valores mediante la asignación

El modo de trabajo con datos definidos como ficheros presenta unas características muy especiales…

14Diego Gutiérrez

Modos de trabajo

Modo escriturao construcción

Se construye la secuencia de datos mediante la incorporación de datos al final de la secuencia actual

• escribir (s, expresión) fI ← fI • < expresión >

• escribir (expresión) fI ← fI • < expresión >

fI fD

primero(fD)

f

15Diego Gutiérrez

Escritura (o construcción) de un fichero secuencial

Se dispone de dos operaciones: los procedimientos iniciarEscrituray escribir

iniciarEscritura: permite establecer el modo de trabajo de escritura o construcción sobre la variable fichero secuencial que figura como argumento en su invocación a la vez que asigna a dicha variable una secuencia de datos vacía

iniciarEscritura(f);

(modoTrabajo(f)=escritura) ^ (f=<>)

16Diego Gutiérrez

Escritura (o construcción) de un fichero secuencial

Se dispone de dos operaciones: los procedimientos iniciarEscrituray escribir

iniciarEscritura: permite establecer el modo de trabajo de escritura o construcción sobre la variable fichero secuencial que figura como argumento en su invocación a la vez que asigna a dicha variable una secuencia de datos vacía!

iniciarEscritura(f);

(modoTrabajo(f)=escritura) ^ (f=<>)

17Diego Gutiérrez

Escritura (o construcción) de un fichero secuencial

escribir: realiza la adición (escritura) de un dato al fichero, que pasará a ser el último elemento de la secuencia de datos que almacena.

escribir(f, expresión);secuencia(f):= secuencia(f)•<expresión>;

Sólo puede invocarse sobre una variable que sea un fichero secuencial f en modo de escritura, es decir, que satisfaga la relación modoTrabajo(f)=escritura

18Diego Gutiérrez

Escritura (o construcción) de un fichero secuencial

algoritmo construirFichero (ES f:tpFichero){ Pre: ---

Post: El fichero “f” almacena una secuencia de datosobtenidos por el procedimiento “obtenerDato” }

variablesdato:tpDato;

principioiniciarEscritura(f); obtenerDato(dato);mientrasQue ¬final(dato) hacer

escribir(f,dato); obtenerDato(dato);finMQ

Fin.

19Diego Gutiérrez

Modos de trabajo

Modo inspección(o lectura)

Accedemos a la secuencia de datos almacenados comenzando por el primero y avanzando uno a uno

fi fd

primero(fD)

• leer (s, variable) variable ← primero(fD)fI ← fI • <primero(fD)>; fD ← resto(fD)

ERROR si finSecuencia

• leer (variable) variable ← primero(fD)fI ← fI • <primero(fD)>; fD ← resto(fD)

ERROR si finSecuencia

20Diego Gutiérrez

Lectura (o inspección) de un fichero secuencial

Recordemos: fI: subsecuencia de elementos del fichero f que ya han sido leídosfD: subsecuencia de elementos pendientes aún de ser leídosf puede verse, desde un punto de vista formal, como una concatenación de las dos secuencias fI y fD: f = fI • fD

Se dispone de tres operaciones: los procedimientos iniciarLecturay leer y la función finFichero

21Diego Gutiérrez

Lectura (o inspección) de un fichero secuencial

iniciarLectura: establece el modo de trabajo de lectura sobre la variable fichero secuencial que figura como argumento en su invocación; además, dispone el proceso para su inspección de forma que el dato que sea accedido en la primera operación de lectura sea el primer dato almacenado en el fichero

iniciarLectura(f);

(modoTrabajo(f)=lectura) ^ (fI=<>) ^ (fD=f)

22Diego Gutiérrez

Lectura (o inspección) de un fichero secuencial

leer: Lee el siguiente dato almacenado en el fichero f y asigna su valor a variable; además, dispone al fichero f para que, en la proxima operación de lectura, sea accedido el dato siguiente al que acaba de ser leído

leer(f,variable);variable:= primero(fD);

fI:= fI•primero(fD); fD:= resto(fD);

Sólo puede invocarse sobre una variable f que sea un fichero secuencial en modo de lectura, es decir, que satisfaga la relación modoTrabajo(f)=lectura

23Diego Gutiérrez

Lectura (o inspección) de un fichero secuencial

finFichero: Devuelve un valor cierto si y sólo si en el recorrido actual del fichero se ha alcanzado el final de la secuencia de datos almacenada en él (marca de fin de fichero)

finFichero(f);finFichero(f) = (fD=<>)

puede invocarse sobre una variable fichero f en cualquiera de sus modo de trabajo lectura o escritura

24Diego Gutiérrez

Lectura (o inspección) de un fichero secuencial

algoritmo inspecionarFichero (ES f:tpFichero){ Pre: ---

Post: Han sido inspeccionados los datosalmacenados en el fichero “f” }

variablesdato:tpDato;

principioiniciarLectura(f);mientrasQue ¬finFichero(f) hacer

leer(f,dato); inspeccionar(dato);finMQ

Fin.

25Diego Gutiérrez

La lectura/escritura de varios datos se podrá denotar enforma condensada:

leer(f, v1, v2,.., vn) leer(f, v1); leer(f, v2); ..; leer(f, vn);escribir(f, e1, e2,.., en) escribir(f,e1);..;escribir(f,en);

26Diego Gutiérrez

Creación e inspección de ficheros físicos

Un fichero lógico es una estructura de datos de tipo fichero cuyo ámbito de utilización se reduce al algoritmo en que estádefinida dicho fichero. Todas las variables de tipo fichero que se han definido hasta ahora son ficheros lógicos y, por tanto, sólo son conocidas dentro del algoritmo.Sus datos no sobreviven después de concluir la ejecución de éstos.

Y entonces?????

27Diego Gutiérrez

Uno de los aspectos más interesantes de este tipo de estructura de datos consiste en su almacenamiento permanente para su posterior utilización.

Debe asociársele primero un fichero físico gestionado por el sistema operativo.

28Diego Gutiérrez

Los ficheros físicos son estructuras de datos análogas a los ficheros lógicos. Se caracterizan por ser gestionadas por el sistema operativo del computador y, por lo tanto, tener un ciclode vida independiente de los programas que puedan trabajar con ellos.

Conexión lógica fichero_lógico– fichero_físico

29Diego Gutiérrez

Conexión lógica fichero_lógico – fichero_físico

Crear un fichero físico desde un algoritmo (programa). Leer desde un algoritmo (programa) la información almacenada en un fichero físico preexistente.

Procedimientos asociar y disociar

30Diego Gutiérrez

asociar(f,nombreExternoFichero);

Establece una conexión lógica entre la variable f, fichero interno gestionado por el programa, y un fichero externo gestionado por el sistema operativo, definido por la expresión nombreExternoFichero(nombre del fichero según el sistema operativo)

La sintaxis de este nombre se deberá ajustar a las reglas definidas por dicho sistema operativo.

31Diego Gutiérrez

disociar(f);

Pone fin a la última conexión lógica establecida previamente entre la variable f (fichero interno gestionado por el programa) y un fichero externo gestionado por el sistema operativo.

Después de ejecutar este procedimiento, la variable f puede ser asociada a otro fichero externo.

32Diego Gutiérrez

Creación de un fichero externo desde un programa

Almacenar en un fichero de datos de tipo entero cuyo nombre externo es MiPrimerFichero.dat los números naturales comprendidos entre el número 1 y el número que determine interactivamente el usuario.

33Diego Gutiérrez

Creación de un fichero externo desde un programa

algoritmo crearFicheroEnteros{ Pre: ---Post: Almacenados en un fichero externo de nombre “MiPrimerFichero.dat” los números naturalescomprendidos en el intervalo[1,maximo]. El valor de máximo es obtenido de forma interactiva }tipos

tpFicheroEnteros = fichero de entero;variables

fichEnteros: tpFicheroEnteros; { Fichero a crear }máximo: entero; { Último entero a almacenar }número: entero; { Siguiente valor a almacenar }

principioescribirCadena(pantalla,“Último número a almacenar en el fichero : ”);leerEntero(teclado,maximo);asociar(fichEnteros,“MiPrimerFichero.dat”);iniciarEscritura(fichEnteros);número:= 0; mientrasQue ¬(número=maximo) hacer

número:= número+1; escribir(fichEnteros, número);finMQdisociar(fichEnteros);

Fin.

34Diego Gutiérrez

Lectura de un fichero externo desde un programa

Escribir por pantalla los datos almacenados en el fichero de datos enteros cuyo nombre externo es MiPrimerFichero.dat

35Diego Gutiérrez

Lectura de un fichero externo desde un programa

algoritmo listarFicheroEnteros{ Pre: Existe el fichero externo “MiPrimerFichero.dat”

Post: Listado por pantalla con los datos almacenados en el fichero externos de datos enteros denombre “MiPrimerFichero.dat” a razón de un dato por línea }tipos

tpFicheroEnteros = fichero de entero;variables

fichEnteros: tpFicheroEnteros;número: entero; { Último dato leído del fichero }

principioasociar(fichEnteros, “MiPrimerFichero.dat”)iniciarLectura(fichEnteros);mientrasQue ¬finFichero(fichEnteros) hacer

leer(fichEnteros, número);escribirEntero(pantalla, número);acabarLínea(pantalla);

finMQdisociar(fichEnteros);

fin

36Diego Gutiérrez

Lectura de un fichero y creación de otrosalgoritmo CreaParesImpares{ Pre: Existe el fichero externo “datos.dat”

Post: Almacenados los datos pares en el fichero externo “pares.dat” y los datos impares en“impares.dat” }

tipostpFicheroEnteros = fichero de entero;

variablesfDatos, fResultados: tpFicheroEnteros; { Ficheros internos }unDato: entero; { Último dato leído }

principioasociar(fDatos, “datos.dat”); iniciarLectura (fDatos);asociar(fResultados, “impares.dat”);IniciarEscritura (fResultados);mientrasQue ¬finFichero(fDatos) hacer

leer(fDatos,unDato);si ¬(unDato mod 2=0) entonces escribir(fResultados,unDato); finSi finMQ

disociar(fResultados);iniciarLectura(fDatos);asociar(fResultados, “pares.dat”);iniciarEscritura(fResultados);mientrasQue ¬finFichero(fDatos) hacer

leer(fDatos,unDato);si unDato mod 2=0 entonces escribir(fResultados,unDato); finSi finMQ

disociar(fResultados); disociar(fDatos);Fin.

37Diego Gutiérrez

Tratamiento de secuencias

Ejemplo:

Contar el número de subsecuencias de datos consecutivos de valores no decrecientes (≤) en un fichero secuencial

38Diego Gutiérrez

Claves que permiten resolver el problema:

1. identificar que la solución del problema puede plantearse como un algoritmo de recorrido completo de la secuencia, manteniendo en cada iteración el conocimiento de los valores de los dos últimos datos leídos (penúltimo y último)

2. identificar que la condición penúltimo>último permite concluir el comienzo de una nueva subsecuencia

3. aplicar el segundo de los esquemas presentados en la lección anterior (particularidad: si la secuencia es no vacía, el valor inicial de la cuenta de subsecuencias ordenadas debe ser igual a uno)

39Diego Gutiérrez

algoritmo contarSubsecuencias (ES f:tpFichero; ES cuenta:entero){ Pre: ---

Post: El valor de “cuenta” es igual al número de subsecuencias de datos consecutivos de valor no decreciente (≤) almacenadas de “f” }

variablespenúltimo,último: tpD;

principioiniciarLectura(f);si ¬finFichero(f) entonces { “f” almacena uno o más datos }

leer(f,último); cuenta:=1;mientrasQue ¬finFichero(f) hacer { trata un nuevo dato de “f” }

penúltimo:=último; leer(f,último);si penúltimo>último entonces { “último” es el primer dato de una nueva

subsecuencia }cuenta:=cuenta+1;

finSifinMQcuenta:=cuentaParcial;si_no { “f” almacena una secuencia vacía }

cuenta:=0;finSi

fin

40Diego Gutiérrez

Ejemplo: Comparación de dos ficheros secuenciales.

Dados dos ficheros de datos de tipo tpFichero, parámetros del procedimiento, devolver a través de un tercer parámetro un valor lógico cierto si y sólo si los contenidos de ambos ficheros son idénticos.

Para ello es necesario que ambos ficheros tengan el mismo número de datos almacenados y que sus elementos homólogos sean iguales.

Recorrido simultáneo de los dos ficheros

41Diego Gutiérrez

algoritmo sonIguales (ES f,g:tpFichero; ES loSon:booleano){ Pre: ---

Post: El parámetro “loSon” toma un valor “cierto” si y sólo los ficheros “f” y “g”almacenan secuencias idénticas de datos }

variablesdatoF,datoG: tpD;iguales: booleano;

principioiniciarLectura(f); iniciarLectura(g);{ Resolución del problema para dos secuencias vacías }iguales:= cierto;mientrasQue ¬finFichero(f) Y ¬finFichero(g) Y iguales hacer{ Compara los siguientes elementos de “f” y ”g” y actualiza la solución del problema

(valor de “iguales”) }leer(f,datoF); leer(g,datoG);iguales:= (datoF=datoG);

finMQloSon:= (iguales Y finFichero(f) Y finFichero(g));

Fin.

42Diego Gutiérrez

Ficheros secuenciales

Conclusiones:

Veremos problemas de búsqueda de un elemento, inserción, o mezcla de ficheros.

Afianzar el uso de ficherosEntender sus limitaciones