Файл, компоненти якого є символами, називається текстовим. Він має стандартний тип Text:
Type Text = File of Char;
Приклади:
Type
ExtClass = File of Person;
CardList = File of Integer;
Var
F : Text;
Data : File of real;
List1, List2 : CardList;
Class10A, Class10B : ExtClass;
Для роботи з нестандартними файлами ім’я файла повинно бути зв’язане з реально існуючим об’єктом – зовнішнім пристроєм. Саме, якщо нам необхідно обробити дані з файла, що знаходиться на магнітному диску і який має (зовнішнє) ім’я D:\ExtName.dat, ми повинні повідомити системі, що працюючи з файлом IntName (читаючи з нього дані або записуючи у нього дані), ми працюємо з файлом ExtName.dat, що знаходиться на диску D:.
Для ототожнення внутрішнього імені файла з зовнішнім іменем використовується процедура Assign(< внутрішнє ім’я >, < 'зовнішнє ім’я ' >).
Після того, як ім’я файла описано і визначено, можна приступити до роботи з файлом. При використанні нестандартних файлів треба пам’ятати, що перед роботою необхідно відкрити їх, тобто зробити доступними з програми. Для цього треба застосувати одну з двох наступних процедур:
Процедура Rewrite(<ім’я файла >) – відкриває файл для запису. Якщо файл раніше існував, всі дані, що зберігались у ньому, знищуються. Файл готовий до запису першої компоненти.
Процедура Reset(<ім’я файла >) – відкриває файл для читання. Файл готовий для читання з нього першої компоненти.
По закінченню роботи з файлом (на запис) він повинен бути закритий. Для цього використовується процедура Close(<ім’я файла >). Ця процедура виконує всі необхідні машинні маніпуляції, що забезпечують збереження даних у файлі.
Для обміну даними з файлами використовують процедури Read і Writе.
Процедура Read (<ім’я файла >,<список введення >), читає дані з файла ( по замовченню ім’я файла - Input). Список введення – це список змінних.
Процедура Writе (<ім’я файла >,<список виведення >), записує дані у файл ( по замовченню ім’я файла - Output). Список виведення – це список виразів.
Якщо F – файл типу Text, то у списку введення/виведення допустимі змінні/вирази типу Integer, Real, Char, String[N]. В інших випадках типи всіх компонент списку повинні співпадати з типом компоненти файла.
При роботі з файлами застосовують стандартні логічні функції:
Eof(F) (end of file) – стандартна функція – признак кінця файла. Якщо файл F вичерпаний, то Eof(F) = True, в протилежному випадку Eof(F) = False.
Eoln(F) (End of line) – стандартна функція – признак кінця рядка текстового файла. Якщо рядок текстового файла F вичерпаний, то Eoln(F) = True, в протилежному випадку Eoln(F) = False. Функція Eoln визначена тільки для файлів типа Text. Звичайно в програмах використовують або текстові файли, або файли, компонентами яких є структуровані дані (наприклад, записи).
Треба пам’ятати, що дані файлових типів неможна використовувати в якості компонент інших структур даних. Наприклад, неможна визначити масив, компонентами якого є файли, запис, полем якої є файл.
Приклад 11.8. Програма формування файла як вибірки з компонент іншого файла. Нехай F - файл записів виду (поле ключа, поле даних). Треба сформувати файл G, який містить ті компоненти F, ключі яких задовольняють умові: значення ключа – ціле число з інтервалу ]Max, Min [.
Program FileForm;
Type
Component = Record
Key: Integer; { поле ключа }
Data: String[20] { поле даних}
End;
OurFile = File of Component;
Var
F, G : OurFile; X: Component;
Max, Min : Integer;
Function Correct(var U: Component): Boolean;
begin
Correct := (U.Key < Max) and (U.Key > Min)
end;
Begin
Read(Max, Min);
Assign(F, 'D:InpFile.dat'); {визначення значення F }
Assign(G, 'D:OutFile.dat'); {визначення значення G }
Reset(F); {файл F відкритий для читання}
Rewrite(G); {файл G відкритий для запису}
While not(Eof(F)) do begin {цикл читання F - запису G}
Read(F, X);
If Correct(X)
then Write(G, X)
end;
Close(G) {файл G закритий}
End.
11.8. Основні задачі обробки файлів
Специфіка файлового типу, яка пов’язана з послідовним доступом до компонент і розташуванням файлів на зовнішніх носіях, накладає жорсткі обмеження на засоби розв’язку задач обробки файлів. Розглянемо деякі такі задачі. Для визначеності будемо вважати, що всі файли мають тип OurFile із приклада 11.3 і впорядковані за значенням ключового поля Key (ключу).
Задача 11.1. Доповнення файла новим елементом. Дано файл F і елемент Х типу Component. Розширити F, включивши в нього компоненту Х з збереженням упорядкованості.
Ось, напевно, єдиний можливий розв’язок:
· Переписувати покомпонентно F у новий файл G до тих пір, поки F^.Key < X.Key ;
· Записати Х у G;
· Переписати “хвіст” файла F і G;
· Перейменувати G у F .
Задача 11.2. Вилучення елемента з файла. Дано файл F і число К - значення ключа елементів, що вилучаються. Скоротити F, вилучивши із нього всі компоненти з ключем К.
Розв’язок аналогічний розв’язку задачі 1:
· Переписувати покомпонентно F у новий файл G до тих пір, поки F^.Key < X.Key;
· Поки F^.Key= К читати F;
· Переписати “хвіст” файла F у G;
· Перейменувати G у F.
Відмітимо, що:
Þ Розв’язки цих задач потребують послідовного пошуку міста елемента Х як компоненти файла. Ефективний розв’язок задачі пошуку (наприклад, бінарний пошук) неможливий.
Þ У якості вихідного використовується новий файл, оскільки читання/запис в один і той же файл неможливі!
Наступні задачі присвячені обробці двох файлів.
Задача 11.3. Злиття (об’єднання) файлів. Дано файли F і G. Треба сформувати файл Н, який містить всі компоненти як F, так і G.
Алгоритм полягає у послідовному і почерговому перегляді файлів F і G і запису чергової компоненти в Н. Почерговість визначається порівнянням значень ключів компонент F і G. Оформимо алгоритм у виді процедури:
Procedure FileMerge(var F, G, H: OurFile);
Var
X, Y : Component;
Flag : Boolean;
Procedure Step(var U:OurFile; var A, B:Component);
begin
Write(H, A);
If Eof(U)
then begin
Write(H, B);
Flag := False
end
else Read(U, A)
end;
Procedure AppendTail(var U: Ourfile);
Var
A: Component;
Begin
While not(Eof(U)) do begin
Read(U, A);
Write(H, A)
end
end;
Begin
Reset(F);
Reset(G);
Rewrite(H);
Flag := True;
Read(F, X);
Read(G, Y);
While Flag do
If X.Key < Y.Key
then Step(F, X, Y)
else Step(G, Y, X);
AppendTail(F);
AppendTail(G);
Close(H)
End;
Задача 11.4. Перетин файлів. Дано файли F і G. Треба сформувати файл Н, який містить всі компоненти, що входять як у F, так і в G.
Задача 11.5. Віднімання файлів. Дано файли F і G. Треба сформувати файл Н, який містить всі компоненти, що входять у F, але не входять у G.
Розв’язок цих задач аналогічний розв’язку задачі злиття файлів.
11.9. Сортування файлів
Упорядкованість компонент файла за одним або кількома ключовими полями – одна з основних умов ефективної реалізації задач обробки файлів. Так, задача роздруку файла у визначеному порядку слідування компонент, якщо файл не впорядкований відповідним чином, розв’язується за допомогою багатократних переглядів (прогонів) файла. Кількість прогонів при цьому пропорційна кількості компонент.
Відсутність прямого доступу до компонент приводить до того, що розглянуті вище алгоритми сортувань масиву неможливо ефективно адаптувати для сортування файла. На відміну від масивів, основні критерії ефективності алгоритму сортування файла – кількість прогонів файлів і кількість проміжних файлів.
Так, наприклад, алгоритм сортування простими обмінами потребує N прогонів файла, що сортується (N – кількість компонент файла). Алгоритм швидкого сортування взагалі не має сенсу розглядати, оскільки при його реалізації необхідно було би читати файл від кінця до початку!
Розглянемо тому новий для нас алгоритм – алгоритм сортування злиттям, який найбільш ефективний при сортуванні файлів і відноситься до швидких алгоритмів при сортуванні масивів, хоча і потребує додаткової пам’яті.
11.9.1. Алгоритм сортування злиттям
Нехай послідовність, що сортується, F = { f1, ..., fN } представлена в виді двох уже відсортованих половин - F1 і F2. Тоді для сортування F достатньо злити (тобто застосувати аналог алгоритму злиття FileMerge) послідовності F1 і F2 у вихідну послідовність G. Оскільки упорядковані половинки F1 і F2 можна отримати за допомогою тих же дій, ми можемо описати алгоритм сортування злиттям рекурсивно. При цьому, очевидно, необхідно використовувати оптимальну кількість проміжних файлів. Оскільки злиття треба починати з однокомпонентних файлів, точна реалізація описаного алгоритму потребує 2N додаткових файлів, що, звичайно, неприйнятно. Тому ми повинні використовувати один файл для збереження декількох послідовностей, що зливаються. Уточнимо цю ідею:
Нехай файл F, що сортується, містить k-елементні упорядковані підпослідовності A1, A2, ..., A2l, k = 2l.
1.Розділ F полягає у переписі послідовностей Aj з парними номерами в файл F1, а з непарними номерами - в файл F2.
Нехай файл F1 містить k-елементні упорядковані підпослідовності B1, B3, ..., B2l-1, а F2 - k-елементні упорядковані підпослідовності B2, B4, ..., B2l.
2.Злиття F1 і F2 полягає в злиттях пар <Bi, Bi+1> у підпослідовності A(i+1) div 2 у файл F. Після обробки F буде містити l 2k-елементних підпослідовностей Aj.
Якщо N - степінь 2-x (N = 2m), то після m-кратного повторення розділення-злиття, починаючи з A1={f1}, ..., AN={fN}, файл F буде містити відсортовану послідовність. У загальному випадку, коли N ¹ 2m, керування злиттями-розділеннями трохи ускладнюється:
* при розділі кількість підпослідовностей може опинитися непарною;
* при злитті остання за рахунком підпослідовність одного з файлів може мати меншу, ніж усі інші, кількість елементів.
Program MergeSort;
Type
Component = Record
Key: Integer; { поле ключа }
Data: String[20] { поле даних}
End;
OurFile = File of Component;
Var
F, F1, F2 : OurFile;
k, L, t, SizeF: Integer;
{Procedure FileOut(var F :OurFile);}
{Procedure FileInp(var F: Ourfile);}
Procedure CopyBlock(Var U, V: OurFile; k: Integer);
Var
i: Integer;
X: Component;
Begin
For i := 1 to k do begin
Read(U, X);
Write(V, X)
end
End;
{ розділення блоками по k компонент F ==> F1, F2 }
Procedure Partition(k: Integer);
Var
i: Integer;
Begin
Reset(F);
Rewrite(F1);
Rewrite(F2);
For i:= 1 to L do
If Odd(i)
then CopyBlock(F, F1, k)
else CopyBlock(F, F2, k);
If Odd(L)
then CopyBlock(F, F2, t)
else CopyBlock(F, F1, t);
Close(F1); Close(F2)
End;
{ злиття блоками по k компонент F1, F2 ==> F }
Procedure Merge(k: Integer);
Var i:
Integer;
Procedure MergeBlock(t: Integer);
Var
count1, count2: Integer;
X1, X2: Component;
Flag: Boolean;
Procedure AppendTail(var U: Ourfile; var p: Integer; s: Integer);
Var
A: Component;
Begin
While p <= s do begin
Read(U, A);
Write(F, A);
p := p + 1
end;
End { AppendTail };
Procedure Step(var U: OurFile;
Var A, B: Component;
var p, q: Integer; s: Integer);
begin
Write(F, A);
p := p + 1;
If p <= s
then Read(U, A)
else begin
Write(F, B);
q := q + 1;
Flag := False
end
end { Step };
Begin { MergeBlock }
count1 := 1;
count2 := 1;
Flag := True;
Read(F1, X1);
Read(F2, X2);
While Flag do
If X1.Key < X2.Key
then Step(F1, X1, X2, count1, count2, k)
else Step(F2, X2, X1, count2, count1, t);
AppendTail(F1, count1, k); AppendTail(F2, count2, t);
end { MergeBlock };
Begin { Merge }
Rewrite(F);
Reset(F1);
Reset(F2);
For i := 1 to (L div 2) do MergeBlock(k);
If t<> 0
then if Odd(L)
then MergeBlock(t)
else CopyBlock(F1, F, t)
else if Odd(L)
then CopyBlock(F1, F, k)
End { Merge };
Procedure FirstPartition;
Var
X : Component;
Begin
Reset(F);
Rewrite(F1);
Rewrite(F2);
SizeF := 0;
While not(Eof(F)) do begin
Read(F, X);
SizeF := Succ(SizeF);
If Odd(SizeF)
then Write(F1, X)
else Write(F2, X)
end;
Close(F1);
Close(F2)
End { FirstPartition };
Begin {Визначення зовнішніх імен файлів F, F1, F2}
FileInp(F);
irstPartition; {перше розділення підрахунком SizeF}
L := SizeF;
t := 0;
Merge(1); {перше злиття1-блоків}
k := 2;
While k < SizeF do begin
L := SizeF div k; {кількість повних k-блоків у F}
t := SizeF mod k; { розмір неповного k-блока }
Partition(k);
Merge(k);
k := 2*k
end;
FileOut(F)
End.
11.9.2. Аналіз складності алгоритму
Оцінимо складність алгоритму в термінах С(n), M(n), L(n), де L(n) – число прогонів файла F і n = SizeF.
1.Оцінка L(n).
L(n)= число розділень + число злиттів. Кожне розділення – виклик процедури Partition, а злиття - виклик Merge. Тому L(n) - подвоєне число повторень тіла циклу While. Звідси, оскільки змінна k, що керує циклом, кожний раз збільшується вдвічі, на L-тому кроку k = 2L, і, отже, L - найбільше число таке, що 2L < n, тобто L = [log2 n].
L(n) = 2[log2n]
2.Оцінка С(n).
Порівняння компонент за ключем відбуваються при злитті. Після кожного порівняння виконується процедура Step, яка записує одну компоненту в F. Тому при кожному злитті кількість порівнянь не перевищує n. Звідси C(n) £ L(n)*n/2, тобто
С(n) £ n [log2 n]
3.Оцінка M(n).
Процедури Partition і Merge пересилають компоненти файлів. Незалежно від значень ключів, виклик кожної з них або читає F, або записує F. Тому M(n) = nL(n), тобто
M(n) = 2n[log2 n]
Отримані оцінки дозволяють класифікувати алгоритм як ефективний алгоритм сортування послідовних файлів. Його також можна адаптувати до сортування масивів.
Алгоритм сортування злиттям може бути поліпшений кількома способами. Розглянемо лише деякі з них:
а. Помітимо (зауважимо), що процедура Partition носить допоміжний характер. Не аналізуючи ключів, вона просто формує файли F1 і F2 для злиття. Тому її можна вилучити, якщо процедуру Merge примусити формувати не F, а одразу F1 і F2. При цьому, звичайно, кількість файлів у програмі збільшується. Саме:
1.F розділимо на (F1, F2).
2.Визначимо допоміжні файли G1, G2
3.Основний цикл алгоритму:
Злиття (F1, F2) ===> (G1, G2);
Злиття (G1, G2) ===> (F1, F2);
(Непарні пари блоків зливаємо на 1-ий файл, парні - на 2-ий).
Складність алгоритму за часом поліпшується майже вдвічі.
б. Зауважимо, що на початковій стадії роботи алгоритму розміри блоків малі. Їх можна сортувати в оперативній пам’яті, використовуючи представлення в виді масиву і швидкі алгоритми сортування масивів. Таким чином, треба змінити процедуру FirstPartition, визначив її як процедуру внутрішнього сортування k0-блоків при деякому (максимально можливому) значенні k0. Цикл While основної програми тепер можна починати з k = k0.
в. В реальних файлах часто зустрічаються вже упорядковані ділянки компонент. Тому файл можна початково розглядати як послідовність упорядкованих ділянок, і зливати не блоки фіксованого розміру, а упорядковані ділянки. Такі сортування називають природними.
11.10. Задача корегування файла
Задача корегування файла є одною з основних задач обробки файлів. Розглянемо її формулювання:
Вихідні дані задачі – файл F, що корегується, файл корегувань G. Результат - відкорегований файл H. Будемо вважати, що файл F має тип OurFile. Тоді файл H має той же тип. Файл корегувань G складається з записів з варіантами:
Type
CorСomponent = record
Key: Integer;
job: (Include, Change, Exclude); {включити, змінити, вилучити}
Case job of
Include, Change: Data: String[20];
Exclude: ()
end
End;
CorFile = File of CorComponent;
Var
G : CorFile;
Це значить, що файл корегувань містить компоненти, які треба включити в основний файл, компоненти, які треба вилучити з файла і компоненти, зміст яких треба змінити (з врахуванням змісту як основного файла, так і файла корегувань).
Файл F вважаємо впорядкованим (за ключем), а файл G, взагалі кажучи, ні. Результатом повинен бути упорядкований відкорегований файл Н.
Розв’язок задачі звичайно містить два етапи:
а) Сортування файла корегувань G;
б) Узагальнене злиття файлів F, G у H.
На практиці файл G може бути невеликим. У цьому випадку застосовують внутрішнє сортування. Узагальнений алгоритм злиття робить всі три варіанта обробки файла F за один прогін.
На завершення відзначимо, що сучасні ЕОМ рідко активно використовують зовнішні носії з послідовним доступом у розв’язках задач керування базами даних, тому структури даних, у яких зберігається інформація, як правило, більш складні, ніж послідовні файли.
11.11. Задачі і вправи
Файли.
Розробіть програму Добавлення елемента до файла.
Розробіть програму Вилучення елемента з файла.
Розробіть програму Перетин файлів.
Розробіть програму Віднімання файлів.
Розробіть програму Корегування файлів.
Розробіть програму корегування упорядкованих файлів, у яких проводиться зміна значень ключових полів. Файл корегувань містить пари
< старий ключ, новий ключ >.
7.Реалізуйте поліпшення a) алгоритму сортування злиттям.
8.Реалізуйте поліпшення в) алгоритму сортування - сортування природним злиттям.
Записи.
Опишіть тип запису – клітинки розкладу занять для своєї спеціальності і курсу. Сформуйте файл двохтижневого розкладу для своєї підгрупи. Розробіть програму, яка визначає кількість лекційних, практичних і лабораторних занять у двохтижневому циклі для своєї підгрупи за вказаною дисципліною.
Опишіть тип запису – відомості про студента групи, необхідні декану факультету. Сформуйте файл студентів своєї підгрупи. Розробіть програму, яка визначає стан успішності в підгрупі.
Опишіть тип запису – відомості про батьків учнів класу, необхідні класному керівнику. Сформуйте файл, що складається не менш, ніж з восьми учнів “Вашого” класу. Розробіть програму, яка за прізвищем і ім’ям учня друкує відомості про його батьків.
Опишіть тип запису – відомості про успішність учня, необхідні для вчителя-предметника зі свого предмета. Сформуйте файл, що складається не менш, ніж з восьми учнів “Вашого” класу. Розробіть програму, яка визначає самого слабшого і самого сильного учня класу.
Опишіть тип запису – рядок залікової книжки (екзаменаційна частина). Сформуйте файл іспитів, зданих Вами. Розробіть програму, яка визначає середній бал, складає список екзаменаторів і за номером семестру роздруковує результати Вашої сесії.
Опишіть тип запису – рядок залікової книжки (залікова частина). Сформуйте файл заліків, зданих Вами. Розробіть програму, яка визначає дні, коли Ви здавали по два і більш заліків.
Опишіть тип запису – відомості про вік, зріст і вагу учня. Сформуйте файл, що складається не менш, ніж з восьми учнів “Вашого класу”. Розробіть програму, яка визначає всіх учнів, що народилися в даний проміжок часу, вказаний датами початку і кінця і визначає середній зріст і середню вагу цієї групи учнів.
Опишіть тип запису – відомості про книгу (наприклад, з інформатики). Сформуйте файл книг, необхідних учителю інформатики. Складіть програму, яка підбирає книги для курсу, номер якого вводиться, друкує імена їх авторів і рік видання.
Опишіть тип запису – відомості про товар у магазині. Сформуйте файл товарів, що є в магазині. Розробіть програму корегування масиву товарів і визначення виручки магазину на даний момент часу.
Опишіть тип запису – рядок у телефонній книзі. Сформуйте файл записів – вашу телефонну записну книжку. Розробіть програму пошуку номера телефона за прізвищем і пошуку адреси за номером телефона.
Файли рядків (слів).
1. Знайти в файлі F всі оборотні слова і скласти з них файл G.
2. Знайти в файлі F входження слова p, замінити їх на слово q, отримавши новий файл G.
3. Знайти в файлі F всі слова, що представляють числа (у десятковому запису) і отримати числовий файл G, що містить знайдені числа.
4. Знайти в файлі F всі однобуквенні слова і зайві пробіли, і, вилучивши їх, отримати новий файл G.
5. Знайти в файлі F всі слова, що зустрічаються більше одного разу, і скласти файл G, вилучивши з F знайдені слова.
6. У файлі F знайти всі слова, що містять подвоєні букви і скласти з них файл G.
7. Знайти в файлі F всі слова, що містять підслово p і скласти з них файл G.
8. Дано файл F. Відсортувати його в алфавітному порядку.
9. Дано слово p і файл F. Знайти в F всі слова, які можна скласти з букв слова p.
12. МНОЖИНИ
12.1. Множинний тип
Ще одним складним стандартним типом даних, визначеним у мові Pascal, є множинний тип. Значенням множинного типу даних є множина, що складається з однотипних елементів. Тип елемента множини називається базовим типом. Базовим типом може бути скалярний або обмежений тип. Таким чином, множина значень множинного типу – це множина всіх підмножин базового типу, враховуючи і порожню множину. Якщо базовий тип містить N елементів, відповідний множинний тип буде містити 2N елементів.
Характерна відміна множинного типу – визначення на ньому найбільш поширених теоретико-множинних операцій і відношень. Це робить множинний тип схожим на прості типи даних. Множинні типи описуються в розділі типів наступним чином:
Type < ім’я типу > = Set of < базовий тип >
