[ЗМІСТ] [Далі] [Назад] [Початок розділу]

7.8. Файли

Слово файл в перекладі з англійської означає папка. Це слово використовують для позначення даних, як правило, значних об'ємів, що зберігаються на пристроях зовнішньої пам'яті: гнучких і жорстких дисках, магнітних стрічках. Така специфіка застосування файлів певним чином відбивається у математичних властивостях файлового виконавця, який корисно порівняти з рядковим виконавцем W (див. п.5.8).

Нехай А - множина. Множина AC всіх послідовностей елементів з А визначається індуктивно:

· порожня послідовність L належить AC;

· якщо а Î А, X Î AC, тоді Xa Î AC - це послідовність, що отримана приписуванням а в кінець послідовності X.

Відмітимо, що ChC=W - множина всіх слів в алфавіті Ch.

На множині всіх послідовностей AC визначені ті ж операції, функції та відношення, що і на множини W всіх слів.

Перерахуємо їх:

1) з'єднання

_ + _: AC, AC -> AC;

2) додавання елемента до початку послідовності

add(_, _): A, AC -> AC;

3) виділення першого елемента послідовності

hd(_): AC -> A;

4) викреслювання першого елемента послідовності

tl(_): AC -> AC;

5) приписування елемента в кінець послідовності

app(_, _): AC, A -> AC;

6) виділення останнього елемента послідовності

lst(_): AC -> A;

7) викреслювання останнього елемента послідовності

bgn(_): AC -> AC;

8) довжина послідовності

len(_): AC -> нат;

9) рівність послідовностей

_ = _: AC, AC -> бул;

Перейдемо тепер від послідовностей до файлів.

7.8.1 Послідовні файли

Нехай t - це тип; D_t - його область; ^ - маркер, що не належить D_t. Послідовним файлом, що складається із записів типу t, називається тип даних t_f

----------------------

¦ тип t_f = файл із t; ¦

L---------------------

областю якого служить множина D_tf, що складається з трійок (A,^,B): двох послідовностей, розділених в точності одним маркером

D_tf = {(А,^,В): А, В Î D_tC}.

Трійку (A,^,B) будемо надалі позначати A^B. Якщо представити, що файл F=А^В, то А називається його початком (lt(F)), В - його закінченням (rt(F)). Послідовність А+В назвемо вмістом файла (ct(F)). Графічно це можна зобразити так

A B

----Т---Т-----Т---- ^ ----Т---Т-----Т----

F ¦ а ¦ b ¦. .. ¦ c ¦ ¦ р ¦ q ¦. .. ¦ r ¦

L---+---+-----+---- L---+---+-----+----

¦ ¦ ¦ ¦

¦<----- lt(F) --->¦ ¦<----- rt(F) --->¦

Файловий виконавець File(t) забезпечує перевірку однієї умови та виконання наступних п’яти інструкцій. Перераховані вище операції над послідовностями, а також позначення lt, rt та ct не реалізовано: вони нам знадобляться для того, щоб пояснити значення наведених нижче конструкцій. (Зрозуміло, ніщо не заважає при необхідності реалізувати їх програмно).

Нехай F - змінна типу файл із t, х - змінна типу t.

1. Відношення:

- кінець файла (End of File)

eof(_): файл із t -> бул

задано тотожністю eof(F) = (rt(F)=L). Графічно істинність умови eof зобразимо так:

А

----Т---Т-----Т---- ^

F ¦ а ¦ b ¦. .. ¦ r ¦ L

L---+---+-----+----

¦ ¦

¦<----- lt(F) --->¦

Очевидно, що в цьому випадку ct(F)=lt(F)=А, rt(F)= L.

2. Інструкції визначимо своїми перед- та післяумовами:

- початок роботи з файлом (файл вже існує)

{ ct(F)=В }

відкрити (F)

{ lt(F)= L & rt(F)=ct(F)=В };

B

^ ----Т---Т-----Т----

F L ¦ а ¦ b ¦. .. ¦ r ¦

L---+---+-----+----

¦ ¦

¦<----- rt(F) --->¦

- створення файла

{ Іст }

створити (F)

{ lt(F)=rt(F)=ct(F)= L };

F L ^ L

- читання одного запису із файла F в змінну х

A B

----Т---Т-----Т---- ^ ----Т---Т-----Т---- -- х --

F ¦ а ¦ b ¦. .. ¦ c ¦ ¦ р ¦ q ¦. .. ¦ r ¦ ¦ ¦

L---+---+-----+---- L---+---+-----+---- L------

¦ ¦ ¦ ¦

¦<----- lt(F) --->¦ ¦<----- rt(F) --->¦

{ lt(F)=А & rt(F)=В & ct(F)=А+В & Øeof(F) }

читати (F, х)

{ lt(F)=app(А,hd(В)) & rt(F)=tl(В) & ct(F)=А+В };

A B

----Т---Т-----Т---Т---- ^ ----Т-----Т---- -- х --

F ¦ а ¦ b ¦. .. ¦ c ¦ р ¦ ¦ q ¦. .. ¦ r ¦ ¦ р ¦

L---+---+-----+---+---- L---+-----+---- L------

¦ ¦ ¦ ¦

¦<------ lt(F) ------>¦ ¦<-- rt(F) -->¦

- дописування в кінець файла F значення змінної х

А

----Т---Т-----Т---- ^ -- х --

F ¦ а ¦ b ¦. .. ¦ r ¦ L ¦ s ¦

L---+---+-----+---- L------

¦ ¦

¦<---- lt(F) ---->¦

{ lt(F)=А & eof(F) }

писати (F, х)

{ lt(F)=app(А,х) & eof(F) }

А

----Т---Т-----Т---Т---- ^ -- х --

F ¦ а ¦ b ¦. .. ¦ r ¦ s ¦ L ¦ s ¦

L---+---+-----+---+---- L------

¦ ¦

¦<------ lt(F) ------>¦

- завершення роботи з файлом

{ F = A^В }

закрити (F)

{ ct(F)=A+В };

Робота з файлами відрізняється від роботи з іншими типами даних. Так можна сказати, що до відкриття або створення файлу а також після його закриття файл як такий недоступний, він не містить маркер і можна казати тільки про послідовність, яка є вмістом файла, але не про сам файл.

Розглянемо деякі типові задачі обробки файлів.

При оформленні підпрограм для роботи з файлами необхідно пам’ятати, що внаслідок відсутності присвоєння, файловий параметр може бути тільки параметром-змінною. Інші способи передачі файлів - аргументи, результати, модифіковані параметри - недоступні.

Приклад 7.13. По масиву А, що містить коефіцієнти многочлена

n n-1

Р (х) = а х + а х +. .. + а х + а, а <> 0,

n 0 1 n-1 n 0

побудувати файл, що містить послідовність його елементів.

процедура PF ( арг А: масив [0..N] із дійсн;

змін F: файл із дійсн ) це

змін I: нат;

поч

створити (F);

для I<-0 до N повт

писати (F, А[I])

кц

кп.

Частіше за все файл складається з величин типу запис. Звідси, до речі, стався сам термін для позначення типу даних, який природніше було б називати декартовим добутком типів.

Для простоти позначень обмежимося записом, що містить два поля

тип t = запис

Ключ: t; (7.6)

s: q

кз;

причому t - простий тип.

Приклад 7.14. Об'єднання двох файлів ct(Н) = ct(F)+ct(G).

процедура Union (змін F, G, Н: файл із t) це

змін X: t;

поч

відкрити (F); відкрити (G); створити (Н);

поки Øeof(F) повт

читати (F, X); писати (Н, X)

кц;

поки Øeof(G) повт

читати (G, X); писати (Н, X)

кц;

закрити(F);закрити(G); закрити(H)

кп.

Файл F називається початком файла G, якщо знайдеться така послідовність А, що ct(F)+А = ct(G).

Приклад 7.15. Початок файла.

процедура BeginF (змін Q: бул; F, G: файл із t) це

змін X, Y: t;

поч

відкрити (F); відкрити (G);

Q <- Іст;

поки Øeof(F) & Q повт

Q <- Øeof(G);

якщо Q то

читати (F, X); читати (G, Y);

Q <- X=Y

кр

кц;

закрити(F);закрити(G)

кп.

Приклад 7.16. Пошук запису за значенням ключа.

процедура SearchF (арг K: t;

змін F: файл із t;

Успіх: бул; Y: q) це

змін X: t;

поч

відкрити (F); Успіх <- Хиб;

поки Ø(eof(F) V Успіх) повт

читати (F, X);

Успіх <- X.Ключ=K;

кц;

якщо Успіх то Y <- X.s кр;

закрити(F)

кп.

7.8.2 Файли прямого доступу

У деяких задачах обробки файлів доцільно мати можливість доступу до довільного запису файла так, як це зроблено у масивах. Для розв’язку цих задач використовують файли прямого доступу.

Нехай t - це тип; D_t - його область; ^ - маркер, що не належить D_t. Файлом прямого доступу, що складається із записів типу t, називається тип даних t_d

---------------------------

¦ тип t_d = прям файл із t; ¦

L--------------------------

Область файла прямого доступу визначається аналогічно області послідовних файлів.

D_td = {(А,^,В): А, В Î D_tC}.

Відношення “eof” та інструкції “відкрити”, “створити”, “читати”, “закрити” залишаються визначеними та мають той же зміст, що й для послідовних файлів.

Для інструкції запису у файл розглядаються 2 випадки:

a)маркер знаходиться в кінці файла (запис у файл аналогічний запису у послідовний файл)

А

----Т---Т-----Т---- ^ -- х --

F ¦ а ¦ b ¦. .. ¦ r ¦ L ¦ s ¦

L---+---+-----+---- L------

¦ ¦

¦<---- lt(F) ---->¦

{ lt(F)=А & eof(F) }

писати (F, х)

{ lt(F)=app(А,х) & eof(F) }

А

----Т---Т-----Т---Т---- ^ -- х --

F ¦ а ¦ b ¦. .. ¦ r ¦ s ¦ L ¦ s ¦

L---+---+-----+---+---- L------

¦ ¦

¦<------ lt(F) ------>¦

b)маркер знаходиться всередині файла

A B

----Т---Т-----Т---- ^ ----Т---Т-----Т---- -- х --

F ¦ а ¦ b ¦. .. ¦ c ¦ ¦ р ¦ q ¦. .. ¦ r ¦ ¦ s ¦

L---+---+-----+---- L---+---+-----+---- L------

¦ ¦ ¦ ¦

¦<----- lt(F) --->¦ ¦<----- rt(F) --->¦

{ lt(F)=А & rt(F) = B & Øeof(F) }

писати (F, х)

{ lt(F)=app(А,s) & rt(F)=tl(B) & Øeof(F) }

A B

----Т---Т-----Т---Т---- ^ ----Т-----Т---- -- х --

F ¦ а ¦ b ¦. .. ¦ c ¦ s ¦ ¦ q ¦. .. ¦ r ¦ ¦ s ¦

L---+---+-----+---+---- L---+-----+---- L------

¦ ¦ ¦ ¦

¦<------ lt(F) ------>¦ ¦<-- rt(F) -->¦

Додатково визначені:

1. Операції:

- довжина файла (кількість записів у файлі)

довжина(_): прям файл із t -> нат

- позиція маркера у файлі (номер запису, перед яким розташовано маркер, починаючи з 0)

позиція(_): прям файл із t -> нат

позиція 0 1 ... i-1 i

----Т---Т-----Т---- ^ ----Т---Т-----Т----

F ¦ а ¦ b ¦. .. ¦ c ¦ ¦ р ¦ q ¦. .. ¦ r ¦

L---+---+-----+---- L---+---+-----+----

¦ ¦ ¦ ¦

¦<----- lt(F) --->¦ ¦<----- rt(F) --->¦

2. Інструкції:

- встановити маркер у задану позицію

0 A i-1 i B

----Т---Т-----Т---Т---Т-----Т---Т ^ ----Т-----Т----

F ¦ а ¦ b ¦. .. ¦ c ¦ d ¦. .. ¦ e ¦ ¦ q ¦. .. ¦ r ¦

L---+---+-----+---+---+-----+---- L---+-----+----

¦ ¦ ¦ ¦

¦<----------- lt(F) ----------->¦ ¦<-- rt(F) -->¦

{ lt(F)=А & rt(F) = B & ct(F) = A+B }

встановити (F, i)

{ len(lt(F))=i & ct(F) = A+B }

0 i-1 i

----Т---Т-----Т---Т ^ ---Т-----Т---Т----Т-----Т----

F ¦ а ¦ b ¦. .. ¦ c ¦ ¦ d ¦. .. ¦ e ¦ q ¦. .. ¦ r ¦

L---+---+-----+---- L---+-----+---+---+-----+----

¦ ¦ ¦ ¦

¦<---- lt(F) ---->¦ ¦<--------- rt(F) --------->¦

Інструкція встановити (F, i) дає відмову при i>довжина(F).

Приклад 7.17. Замінити всі записи файла із значенням ключа K заданим записом Y (тип записів файла t описано у (7.6)).

процедура ReplaceF (арг K: t; Y: q;

змін F: прям файл із t) це

змін X: t; I: нат;

поч

відкрити (F);

для I <- 0 до довжина(F)-1 повт

читати (F,X);

якщо X.Ключ=K то

встановити(F,I); писати(F,Y)

кр

кц;

закрити(F)

кп.

Хоча файли прямого доступу надають можливість переходу до довільного запису файла, користуватися цією можливістю слід обережно, тому що вартість інструкції “встановити” є високою.

7.8.3 Текстові файли

Текстові файли є частковим випадком послідовних файлів. Їх виділяють у окремий тип через велику кількість задач, які пов’язані з обробкою текстів. Текстовий файл складається з символів, які поділяються (умовно) на рядки змінної довжини за допомогою спеціального символа завершення рядка. Цей символ ми будемо позначати ‘#’. Отже, областю текстових файлів є

D_txt = {(А,^,В): А, В Î ChC}.

Опис змінних для текстових файлів виглядає так:

змін F: текст;

Відношення “eof” та інструкції “відкрити”, “створити”, “закрити” залишаються визначеними та мають той же зміст, що й для послідовних файлів.

Додатково для текстових файлів визначено:

1. Відношення:

- кінець рядка

eoln(_): файл із t -> бул

задано тотожністю eoln(F) = (hd(rt(F))=’#’). Графічно істинність умови eoln зобразимо так:

A B

----Т---Т-----Т---- ^ ----Т---Т-----Т----

F ¦ а ¦ b ¦. .. ¦ c ¦ ¦ # ¦ q ¦. .. ¦ r ¦

L---+---+-----+---- L---+---+-----+----

¦ ¦ ¦ ¦

¦<----- lt(F) --->¦ ¦<----- rt(F) --->¦

2. Інструкції:

- читати з текстового файла читати(F,x), де x – символ або рядок.

a)x - символ

A B

----Т---Т-----Т---- ^ ----Т---T---Т-----Т---- -- х --

F ¦ а ¦ b ¦. .. ¦ c ¦ ¦ р ¦ q ¦ # ¦. .. ¦ r ¦ ¦ ¦

L---+---+-----+---- L---+---+---+-----+---- L------

¦ ¦ ¦ ¦

¦<----- lt(F) --->¦ ¦<------- rt(F) ----->¦

{ lt(F)=А & rt(F) = B & Øeof(F) }

читати (F, х)

{ lt(F)=app(А,hd(B)) & rt(F)=tl(B) & x=hd(B) }

A B

----Т---Т-----Т---Т---- ^ ----T---Т-----Т---- -- х --

F ¦ а ¦ b ¦. .. ¦ c ¦ p ¦ ¦ q ¦ # ¦. .. ¦ r ¦ ¦ p ¦

L---+---+-----+---+---- L---+---+-----+---- L------

¦ ¦ ¦ ¦

¦<------ lt(F) ------>¦ ¦<---- rt(F) ---->¦

b)x - рядок

A B

----Т---Т-----Т---- ^ ----Т---T---Т-----Т---- -- х --

F ¦ а ¦ b ¦. .. ¦ c ¦ ¦ р ¦ q ¦ # ¦. .. ¦ r ¦ ¦ ¦

L---+---+-----+---- L---+---+---+-----+---- L------

¦ ¦ ¦ ¦

¦<----- lt(F) --->¦ ¦<------- rt(F) ----->¦

{ lt(F)=А & rt(F) = B & Øeof(F) & B = C+’#’+D }

читати (F, х)

{ lt(F)=А+C & rt(F)=’#’+D & x=C }

A B

----Т---Т-----Т---Т---T---- ^ ----Т-----Т---- -- х ---

F ¦ а ¦ b ¦. .. ¦ c ¦ p ¦ q ¦ ¦ # ¦. .. ¦ r ¦ ¦ pq ¦

L---+---+-----+---+---+ - L---+-----+---- L-------

¦ ¦ ¦ ¦

¦<-------- lt(F) -------->¦ ¦<-- rt(F) -->¦

- читати до кінця рядка читати#(F,x), де x – символ або рядок.

a)x – символ; читається поточний символ після маркера, маркер встановлюється на початок нового рядка файла.

A B

----Т---Т-----Т---- ^ ----Т---T---Т-----Т---- -- х --

F ¦ а ¦ b ¦. .. ¦ c ¦ ¦ р ¦ q ¦ # ¦. .. ¦ r ¦ ¦ ¦

L---+---+-----+---- L---+---+---+-----+---- L------

¦ ¦ ¦ ¦

¦<----- lt(F) --->¦ ¦<------- rt(F) ----->¦

{ lt(F)=А & rt(F) = B & Øeof(F) & B = C+’#’+D }

читати# (F, х)

{ lt(F)=А+C+’#’ & rt(F)=D & x=hd(B) }

A B

----Т---Т-----Т---Т---T---T---Т ^ ------Т---- -- х --

F ¦ а ¦ b ¦. .. ¦ c ¦ p ¦ q ¦ # ¦ ¦. .. ¦ r ¦ ¦ p ¦

L---+---+-----+---+---+---+---- L-----+---- L------

¦ ¦ ¦ ¦

¦<---------- lt(F) ---------->¦ ¦< rt(F) >¦

b)x – рядок; читаються всі символи після маркера до кінця рядка, маркер встановлюється на початок нового рядка.

A B

----Т---Т-----Т---- ^ ----Т---T---Т-----Т---- -- х --

F ¦ а ¦ b ¦. .. ¦ c ¦ ¦ р ¦ q ¦ # ¦. .. ¦ r ¦ ¦ ¦

L---+---+-----+---- L---+---+---+-----+---- L------

¦ ¦ ¦ ¦

¦<----- lt(F) --->¦ ¦<------- rt(F) ----->¦

{ lt(F)=А & rt(F) = B & Øeof(F) & B = C+’#’+D }

читати# (F, х)

{ lt(F)=А+C+’#’ & rt(F)=D & x=C }

A B

----Т---Т-----Т---Т---T---- ^ ----Т-----Т---- -- х ---

F ¦ а ¦ b ¦. .. ¦ c ¦ p ¦ q ¦ ¦ # ¦. .. ¦ r ¦ ¦ pq ¦

L---+---+-----+---+---+ - L---+-----+---- L-------

¦ ¦ ¦ ¦

¦<-------- lt(F) -------->¦ ¦<-- rt(F) -->¦

- писати у текстовий файл писати(F,x), де x – символ або рядок.

a)x - символ

А

----Т---Т-----Т---- ^ -- х --

F ¦ а ¦ b ¦. .. ¦ r ¦ L ¦ s ¦

L---+---+-----+---- L------

¦ ¦

¦<---- lt(F) ---->¦

{ lt(F)=А & eof(F) }

писати (F, х)

{ lt(F)=app(А,х) & eof(F) }

А

----Т---Т-----Т---Т---- ^ -- х --

F ¦ а ¦ b ¦. .. ¦ r ¦ s ¦ L ¦ s ¦

L---+---+-----+---+---- L------

¦ ¦

¦<------ lt(F) ------>¦

b)x - рядок

А

----Т---Т-----Т---- ^ -- х --

F ¦ а ¦ b ¦. .. ¦ r ¦ L ¦ st ¦

L---+---+-----+---- L------

¦ ¦

¦<---- lt(F) ---->¦

{ lt(F)=А & eof(F) }

писати (F, х)

{ lt(F)=А+х & eof(F) }

А

----Т---Т-----Т---Т---T---- ^ -- х --

F ¦ а ¦ b ¦. .. ¦ r ¦ s ¦ t ¦ L ¦ st ¦

L---+---+-----+---+---+---- L------

¦ ¦

¦<-------- lt(F) -------->¦

- писати до кінця рядка писати#(F,x), де x – символ або рядок.

a)x - символ

А

----Т---Т-----Т---- ^ -- х --

F ¦ а ¦ b ¦. .. ¦ r ¦ L ¦ s ¦

L---+---+-----+---- L------

¦ ¦

¦<---- lt(F) ---->¦

{ lt(F)=А & eof(F) }

писати# (F, х)

{ lt(F)=app(app(А,х),’#’) & eof(F) }

А

----Т---Т-----Т---Т---T---- ^ -- х --

F ¦ а ¦ b ¦. .. ¦ r ¦ s ¦ # ¦ L ¦ s ¦

L---+---+-----+---+---+---- L------

¦ ¦

¦<-------- lt(F) -------->¦

b)x - рядок

А

----Т---Т-----Т---- ^ -- х --

F ¦ а ¦ b ¦. .. ¦ r ¦ L ¦ st ¦

L---+---+-----+---- L------

¦ ¦

¦<---- lt(F) ---->¦

{ lt(F)=А & eof(F) }

писати# (F, х)

{ lt(F)=А+х+’#’ & eof(F) }

А

----Т---Т-----Т---Т---T---- ^ -- х --

F ¦ а ¦ b ¦. .. ¦ r ¦ s ¦ t ¦ L ¦ st ¦

L---+---+-----+---+---+---- L------

¦ ¦

¦<-------- lt(F) -------->¦

Інструкцію читання або запису до кінця рядка можна також використовувати з одним параметром – файлом, наприклад, читати#(F) або писати#(F). В цьому випадку виконавець пропускає всі символи файла, включаючи кінець рядка, при читанні, та записує у файл символ кінця радка при записі.

Приклад 7.18. Замінити всі входження у текстовий файл символа c рядком A.

процедура ReplaceText (арг c: симв; A: рядок;

змін F,G: текст) це

функція Replace(S, A: рядок c: симв): рядок це

змін S1: рядок;

поч

S1 <- ‘’

поки S <> ‘’ повт

якщо hd(S) = c то S1 <- S1+A

інакше S1 <- app(S1,hd(S)) кр;

S <- tl(S)

кц;

Replace <- S1

кф;

змін S, S1: рядок;

поч

відкрити (F); створити(G);

поки Øeof(F) повт

читати#(F,S);

S1 <- Replace(S,A,c);

писати#(G,S1)

кц;

закрити(F); закрити(G)

кп.

[ЗМІСТ] [Далі] [Назад] [Початок розділу]