§1. Записи
Запис - це структурований тип даних, що об'єднує в собі елементи (поля запису) одного або різного типу. Визначення типу запис починається ідентифікатором RECORD і закінчується словом END. Між ними записується список елементів, які називаються полями, із за наченням ім’я поля і типом кожного поля.
Приклад запису, що містить інформацію про день народження.
Type
Day=1..31;
Month=1..12;
Era=1900..2000;
Date=Record
; Month=1..12;
Era=1900..2000;
Date=Record
Chislo : Day;
Mesayc : Month;
God : Era;
End;
Над записами припустимі операції присвоєння, перевірки на рівність і нерівність, ввід та вивід Chislo : Day;
Mesayc : Month;
God : Era;
End;
Над записами припустимі операції присвоєння, перевірки на рівність і нерівність, ввід та вивід.
З полем запису у програмі можна обходитись, як із змінною того ж типу, що поле. Звертатися до поля по складовому імені:
ім'я запису. ім'я поля
Робота з записами
Program Rec;
Type
Book = record
Tittle: string [80]; {назва}
Author: string [20]; {автор}
p; God : Era;
End;
Над записами припустимі операції присвоєння, перевірки на рівність і нерівність, ввід та вивід.
З полем запису у програмі можна обходитись, як із змінною того ж типу, що поле. Звертатися до поля по складовому імені:
ім'я запису. ім'я поля
Робота з записами
Program Rec;
Type
Book = record
Tittle: string [80]; {назва}
Author: string [20]; {автор}
Year : integer; {рік видання}
End;
Var
X,Y: Book;
Z: Array [1.. 100] Of Book;
Begin
X.Tittle:='Війна та мир';
X.Author:=‘Толстой';
X.Year:=1980;
Y:=X'
WriteLn(Y. Head, Y. Author);
Z[5]:=X
End.
Тип поля може бути довільним, у тому числі і записом. Наприклад:
Type
Full Name=Record
Surname: String;
Name: String[20];
End;
Book=Record
Tittle: String;
Author: Full Name;
Year: Integer;
End
Якщо поле є записом, звертання до його елементів відбувається по імені, що складається з трьох частин, наприклад, X.Author.Surname. Глибина вкладення описів не обмежена.
Оператор WITH
Цей оператор для тих, хто не любить багато писати. Він дозволяє скоротити звертання до полів запису. Його схема така:
WITH ім'я запису DO оператор
Всюди усередині оператора можна опускати ім'я запису в складовому імені поля, транслятор додасть його сам. Приклад застосування оператора WITH.
Type
Bal=2..5;
Month=1..12;
Ocenca=Record
Matem : Bal;
Pedag : Bal;
Phiz : Bal;
End;
Var
Dipl : Ocenca;
…
With Dipl do
Begin
Write('Матeматика - ');
ReadLn(Matem);
Write('Педагогика - ');
ReadLn(Pedag);
Write('Физика - ');
ReadLn(Phiz);
End
Послідовний пошук
Комп'ютер ідеально пристосований для роботи з великим обсягом інформації: телефонним довідником, адресною книгою, бібліотечним каталогом. Для схову такої інформації підходить масив записів.
Подивимося, як знайти інформацію про книгу по заданій ознаці, наприклад, по прізвищу автора. Знайти, значить визначити номер запису в масиві або повідомити про відсутність такого запису.
Самий простий алгоритм пошуку - послідовний. Він полягає в тому, що у всіх записах послідовно, починаючи з першого, перевіряється значення ознаки, по якому ведеться пошук. Нехай потрібно знайти всіх осіб жіночої статі. Це можна зробити так
For I:=1 to N Do
If Body[I].Sex=’ж’ Then WriteLn(I:5, Body[I].Famel)
До закінчення пошуку може виконатись дуже багато циклів, тому час пошуку залежить від числа операцій в одному повторенні.
Двійковий пошук
Загальною властивістю алгоритмів послідовного пошуку є те, що час пошуку прямопропорційний кількості записів. Чи можна шукати швидше? Виявляється що так, якщо масив записів відсортований за значенням шуканої ознаки.
Розглянемо такий алгоритм пошуку слова в словнику.
1. Відчинити словник посередині.
2. Порівняти шукане слово з тим, що всередині словника.
3. Якщо слова збігаються, пошук завершений.
4. Якщо слово всередині більше шуканого, продовжити пошук у першій половині словника.
5. Якщо слово всередині менше шуканого, продовжити пошук у другій половині словника.
Слова "продовжити пошук" означають застосування алгоритму в цілому до половини словника. Зрештою, або слово буде знайдено, або поділяти навпіл буде нічого, виходить, слова в словнику немає.
Словник можна зберігати в масиві записів, початок і кінець області пошуку запам'ятовувати в особливих змінних. Запис словника повинен мати окреме поле, значенням якого є слово.
Порівняємо швидкість послідовного і двійкового пошуку. Перший скорочує область пошуку на один запис за кожний крок алгоритму. Другий за один крок зменшує область пошуку вдвічі.
Приклад програми
Program Spisok;
Const
N=15;
Type
Day=1..31;
Bal=2..5;
Month=1..12;
Era=1900..2000;
Ocenca=Record
Matem : Bal;
Pedag : Bal;
Phiz : Bal;
End;
Date=Record
Chislo : Day;
Mesayc : Month;
God : Era;
End;
Student=Record
Famel : String[15];
Name : String[15];
Born : Date;
Sex : Char;
Dipl : Ocenca;
End;
Var
I : Integer;
Body : Array [1..N] of Student;
BEGIN
For I:=1 to N do
Begin
With Body[I] do
Begin
Write('Фамилия - ');
ReadLn(Famel);
Write('Имя - ');
ReadLn(Name);
Write('Число рождения - ');
ReadLn(Born.Chislo);
Write('Месяц рождения (1 - 12)- ');
ReadLn(Born.Mesayc);
Write('Год рождения - ');
ReadLn(Born.God);
Write('Пол (м/ж) - ');
ReadLn(Sex);
With Dipl do
Begin
Write('Матeматика - ');
ReadLn(Matem);
Write('Педагогика - ');
ReadLn(Pedag);
Write('Физика - ');
ReadLn(Phiz);
End
End;
End;
For I:=1 to N Do
If Body[I].Sex=’ж’ Then WriteLn(I:5, Body[I].Famel)
END. |
