[ЗМІСТ] [Далі] [Назад] [Початок розділу]
7.3. Записи
Найбільш
загальний метод отримання складених
типів полягає в об'єднанні елементів довільних типів. Причому самі ці елементи
можуть бути в свою чергу складеними. Приклад
з математики: комплексні числа, що
складаються з двох дійсних чисел, або
координати точки, що складаються з
двох або більше чисел (залежить від розмірності простору). Або приклад з
обробки даних: особа описується за допомогою декількох
відповідних характеристик на зразок
імені, прізвища, дати народження, статі та сімейного стану.
У
математиці такі складені типи називають
декартовим добутком складаючих його типів. Це пояснюється тим, що множина
значень, визначена таким складеним типом, складається з всіх можливих комбінацій значень, що відносяться до кожної з множин,
які представляють собою складаючі
типи.
Декартів добуток двох множин
- це множина всіх можливих
впорядкованих пар
Т х S = {(t, s): t Î Т, s Î S}.
Якщо, наприклад, Т є {1,6}, а S є {2,4,7}, то їх декартів добуток - це множина { (1,2), (6,2), (1,4), (6,4), (1,7),
(6,7)}, що має 2*3=6 елементів. Операція декартового
множення асоціативна, але не комутативна.
Твердження 7.2. Якщо ¦Т¦=n,
¦S¦=m, то ¦Т х S¦=n*m.¦
Декартів добуток n множин визначимо співвідношенням
Т х
Т х...х Т = Т х (Т х...х Т ).
1
2 n 1
2 n
Твердження 7.3. Якщо ¦Т
¦=m, то ¦Т х...х Т ¦=m *...* m ¦
i
i 1 n
1 n
Замість (t1, (t2, (..., tn
)...) будемо писати просто
(t1, t2, ..., tn), (7.3)
називаючи (7.3) кортежем
або n-кою і вважаючи
Т х
Т х...х Т = {(t, t, ..., t ):
t Î Т,
i=1,2,..., n}.
1
2 n
1 2 n
i i
Проекція - це функція вибору i-ї
координати кортежу
q:
Т х Т х...х Т -> Т,
i
1 2 n
i
причому q (t,
t, ..., t ) = t, i=1,2,..., n.
i
1 2 n
i
Два кортежі рівні
(t, t, ..., t ) = (t', t',..., t')
1
2 n 1
2 n
якщо t =t', t =t',.
.., t =t'.
1
1 2 2
n n
Розглянемо
реалізацію декартових добутків типів.
Структура даних, що обслуговує ці конструкції, отримала назву запису.
Нехай t1, t2, ..., tn - типи; Dt1, Dt2, ..., Dtn - їх області; s1, s2,
..., sn -
ідентифікатори.
Записом tr з полями типів t1, t2, ..., tn помічених селекторами s1, s2, ..., sn, відповідно, назвемо тип даних, областю визначення якого служить декартів добутиок Dt1 х Dt2 х...х Dtn.
Позначення
---------------------------------------
¦ тип
t = запис ¦
¦ r ¦
¦ s:
t; s:
t; ...;s:
t ¦
¦ 1
1 2 2
n n ¦
¦ кінець_запису ¦
L--------------------------------------
Будемо
використовувати скорочення кз замість кінець_запису. Наприклад, точку на площині в декартовій системі координат можна визначити так
тип
Коорд= запис запис
X: дійсн; або X, Y: дійсн
Y: дійсн кз;
кз;
змін Точка: Коорд;
а тип
раціональне число, наприклад, так
тип Раціонал = (N: ціл; D: нат).
Визначимо
відношення, функції та інструкції над
записами.
Нехай
u, v - записи типу tr; е - вираз, що приймає значення типу tr, еk - вирази,
що приймають значення типів tk.
1. Функції:
- проекція
_.s:
t -> t , k=1,2,...,
n,
k
r k
де u.sk = qk(u). Наприклад, значення Точка.Y дорівнює
координаті точки по осі у.
2. Відношення:
- рівність
двох записів як кортежів u = v;
- нерівність
u <> v = Ø(u = v).
3. Інструкції:
- зміна поля запису u.sk <- еk. Наприклад, Точка.X <- 4.7;
- присвоєння
u <- e. Наприклад, якщо змінна Z
описана як така, що має тип Коорд, то після виконання ланцюга
Z.Y <- 2; Точка <- Z
змінна Точка
буде представляти собою пару (1, 2).
Декартовим виконавцем Desc(t1, ..., tn ) назвемо
виконавець, що успадковує можливості
виконавців кожного з типів t1, ..., tn і, крім
того, має в своєму розпорядженні перераховані
вище функції, відношення та інструкції.
Приклад 7.5. Тип комплексні числа:
тип
Компл= запис
Re: дійсн;
Im: дійсн
кз;
Якщо змінна X має тип Компл, то в прийнятих
позначеннях X.Re - її дійсна, а X.Im - уявна частина.
Визначимо деякі функції та процедури над
комплексним типом.
Додавання двох комплексних чисел.
функція
Сума_Компл (X, Y: Компл): Компл це
змін Z: Компл;
поч
Z.Re <- X.Re+Y.Re;
Z.Im <- X.Im+Y.Im;
Сума_Компл <- Z
кф.
Виведення комплексного числа.
процедура
Виведення_Компл (арг X: Компл) це
поч
показати (X.Re);
якщо X.Im >= 0 то показати (' + ')
інакше
показати (' - ') кр;
показати (¦X.Im¦,'*I')
кп.
Приклад
7.6. Дата завтрашнього дня.
Якщо визначити тип дата
таким чином
тип
Рік = нат;
Місяць= (січ, лют, бер, кві, тра, чер,
лип, сер, вер, жов, лис, гру);
Число= 1..31;
Дата = запис
D: Число;
M: Місяць;
Y: Рік
кз,
тривалість
місяця обчислювати за допомогою
підпрограми (приклад 7.1)
функція
Дов_Міс (M: Місяць): Число це
змін Короткий: множ із Місяць;
поч
Короткий <- [кві, чер, вер, лис];
якщо M=лют то Дов_Міс <- 28
інякщо M в Короткий то Дов_Міс
<- 30
інакше
Дов_Міс <- 31 кр
кр
кф,
то для визначення
дати завтрашнього дня можна використати функцію
функція
Завтра (Сьогодні: Дата): Дата це
змін L: Число;
поч
L <- Дов_Міс (Сьогодні.M);
якщо (Сьогодні.M = лют) & (Сьогодні.Y mod 4 = 0) то L <- 29 кр;
якщо (Сьогодні.D = 31) & (Сьогодні.M
= гру) то
Завтра.D <- 1;
Завтра.M <- січ;
Завтра.Y <- Сьогодні.Y+1
інакше
Завтра.Y <- Сьогодні.Y;
якщо Сьогодні.D = L то
Завтра.D <- 1;
Завтра.M <- succ(Сьогодні.M)
інакше
Завтра.D <- Сьогодні.D+1;
Завтра.M <- Сьогодні.M
кр
кр
кф.
7.4 Об’єднання
Розглянемо
об'єднання А = А1 +А2 +...+Аn множин А1, А2, ..., Аn, що попарно неперетинаються. По будь-якому х з
А можна вказати єдину множину Аk, що містить
x. Справедливе
Твердження 7.4. Якщо Аk * Аi = Æ (k
<> i), ¦Аk¦
= mk, то
¦А + А +...+ А ¦ = m + m +...+ m.
1
2 n 1
2 n
Розмічене об'єднання, - стандартний прийом забезпечення умови твердження 7.4.
(i) (i)
(i) (i) (i)
(i)
Нехай z = (s: t; s: t; ...; s: t ), i=1,2,..., n -
i
1 1 2
2 m m
i i
записи;
D, D, ..., D - їх області визначення; крім того, нехай
z
z z
1
2 n n
тип t заданий перерахуванням
t = (а, а, ..., а ), причому а Ï È D
1 2
n i
j=1 z
j
і h - ідентифікатор типу t.
Об'єднанням
типів z1, z2, ..., zn, розміченим дискриминантом
h типу t, назвемо
тип q,
--------------------------
¦ тип
q = вибір
h: t із
¦
¦ |а:
z; ¦
¦ 1
1 ¦
¦ |а:
z; ¦
¦ 2
2 ¦
¦ ... ¦
¦ |а:
z; ¦
¦
n n
¦
¦ кв; ¦
¦ ¦
L-------------------------
областю визначення якого служить об'єднання
множин, що не перетинаються
{а } х D
+ {а } х D + ... + {а } х
D.
1
z 2 z
n z
1 2 n
Отже,
величини типу q - це записи, перше поле яких помічено
селектором h. Набір інших полів залежить від значення першого поля: якщо
значення першого поля рівне аk, то їх набір - це запис типу zk.
Набір
функцій, відношень та інструкцій
залишається тим самим, що й для записів, при
такому уточненні:
Нехай х - змінна типу q, тоді проекції x.sk(i) (k = 1,2,..., mi) мають значення, якщо x.h = аi.
Приклад 7.7. Універсальний комплексний
тип, що допускає як алгебраїчне, так і
тригонометричне представлення:
тип
Компл= вибір C: (алг, трг) із
|алг: (Re, Im: дійсн);
|трг: (R, Phi: дійсн)
кв;
функція
Модуль (Z: Компл): дійсн це
поч
якщо Z.C = трг то Модуль <- Z.R
інакше
Модуль <- sqrt(Z.Re*Z.Re + Z.Im*Z.Im) кр
кф.
Відмітимо,
що при Z.C = трг, запис Z.Re або Z.Im не має значення.
Аналогічно, помилково використати імена Z.R і Z.Phi - при Z.C = алг.
Приклад 7.8. Відстань d між двома
точками а та b, кожна з яких задана в
прямокутній або полярній системі координат.
Тип
Коорд - координат точки тепер можна визначити так
тип
Сист_Коор = (прям, поляр);
Коорд = вибір Сист: Сист_Коор із
|прям: (X, Y: дійсн);
|поляр: (R, Phi: дійсн)
кв.
Для обчислення відстані між точками
використовується наступна функція
функція Dist (A,B: Коорд): дійсн це
поч
вибір
A.Сист із
| прям: вибір B.Сист із
| прям: Dist <- sqrt((A.X-B.X)*(A.X-B.X)+
(A.Y-B.Y)*(A.Y-B.Y));
| поляр: Dist <- sqrt((A.X-B.R*cos(B.Phi))*
(A.X-B.R*cos(B.Phi))+
(A.Y-B.R*sin(B.Phi))*
(A.Y-B.R*sin(B.Phi)))
кв;
| поляр: вибір B.Сист із
| прям: Dist <- sqrt((A.R*cos(A.Phi)-B.X)*
(A.R*cos(A.Phi)-B.X)+
(A.R*sin(A.Phi)-B.Y)*
(A.R*sin(B.Phi)-B.Y));
| поляр: Dist <- sqrt(A.R*A.R+B.R*B.R-2*A.R*B.R*
cos(A.Phi-B.Phi))
кв
кв
кф.
Алгоритм розв’язку
задачі тоді можна представити,
наприклад, так
Алгоритм
Відст_на_Плошині це
тип
Сист_Коор = (прям, поляр);
Коорд = вибір Сист: Сист_Коор із
|прям: (X, Y: дійсн);
|поляр: (R, Phi: дійсн)
кв.
змін А, В: Коорд;
функція
Dist (А, В: Коорд): дійсн це
...
кф;
процедура
Взяти_Точку (рез А: Коорд) це
поч
показати('Система координат [прям, поляр]?:');
взяти(A.Сист);
показати('Її координати по х, у:');
вибір A.Сист із
¦ прям: взяти (A.X, A.Y);
¦ поляр:
взяти (A.R, A.Phi)
кв
кп;
поч
показати('Введення першої точки');
Взяти_Точку(А);
показати('Введення другий точки');
Взяти_Точку(В);
показати('Відстань між ними дорівнює', Dist(А, В))
ка.
7.5. Записи
та об’єднання у мовах програмування
У мові Паскаль запис - це структурований
тип даних, що складається з фіксованого числа компонент різного типу.
Визначення типу запису починається
ідентифікатором record і закінчується зарезервованим словом end. Між ними
розміщується список компонентів, які називають полями, з вказанням
ідентифікаторів полів та типу кожного поля, тобто
type t = record
r s:
t;
1 1
s: t;
2 2
...
s: t
n n
end.
Приклади
описів даних типу запис:
type Date= record
Day: 1..31;
Month: (jan, feb, mar,
apr, may, jun,
jul, aug, sep, oct, nov, dec);
Year: 1900..3000
end;
type Avto= record
Nom: string[7]; (* номер *)
Marka: string[20]; (*
марка автомобіля *)
Color: 1..9; (* колір
автомобіля *)
Name: string[40];
(* П І Пб власника *)
Adress: string[60] (* адреса власника *)
end;
var M, V: Avto; D: Date;
Person: record
Name, FirstName: string[20];
BirthDate: Date;
Sex: (male, female);
MarStatus: (single,
married, widowed, divorced)
end;
Доступ
до полів запису M: M.Nom, M.Marka, M.Color, M.Name, M.Adress.
Вводити-виводити
запис як агрегатний об'єкт - заборонено. Дані дії виконуються для кожного поля окремо.
Для ініціалізації полів запису або зміни
їх значень використовується оператор присвоєння. Допускається присвоювати одному запису значення іншого, якщо вони мають один і
той же тип, наприклад, інструкція M:= V допустима, а запис V:= D помилкова.
Звернення
до полів запису має дещо громіздкий вигляд. Для скорочення запису можна використати оператор with:
with V do
begin
Р
end
де V - змінна типу запис, а Р - оператор. Один раз вказавши
змінну типу запис в операторі with, можна працювати з іменами полів, як із звичайними змінними, тобто без вказанням перед ідентифікатором поля імені змінної, що визначає
запис. Наприклад,
with M do begin
Nom:= '53761КВ';
Marka:= 'ГАЗ-21';
Color:= 9;
Name:= 'Петренко П.П.';
Adress:= 'вул. Стара, 6'
end.
Мова Паскаль допускає
вкладення записів один в одний; відповідно, оператор with також може бути вкладеним.
Приклад 2P. Введення, виведення та
додавання комплексних чисел (задача 7.5).
program COMPL;
type COMPLEX= record
RE, IM: real
end;
var X, Y, Z: COMPLEX;
procedure GET_C (var X: COMPLEX);
begin
write('Дійсна частина числа=? '); readln(X.RE);
write('Уявна частина числа=? '); readln(X.IM)
end;
procedure SUMA (X, Y: COMPLEX; var Z: COMPLEX);
begin
Z.RE:= X.RE+Y.RE; Z.IM:= X.IM+Y.IM
end;
procedure PUT_C (X: COMPLEX);
begin
write(X.RE);
if X.IM>0 then write(' +') else
write(' -');
write(abs(X.IM),' * I')
end;
begin
writeln(' ------ число X:'); GET_C(X);
writeln(' ------ число Y:'); GET_C(Y);
writeln('Сума комплексних чисел дорівнює');
writeln; SUMA(X, Y, Z); PUT_C(Z)
end.
Зверніть
увагу, що для обчислення суми
використовується процедура, а не
програмована функція. Це пов'язано з тим,
що функція у Паскалі не може мати результат складеного типу (COMPLEX).
Для
реалізації розмічених об’єднань у Паскалі використовують записи з варіантами.
Вони складаються з необов'язкової фіксованої
та варіантної частин. Варіантна частина формується за допомогою оператора
case. Він задає особливе поле запису - поле ознаки (дискримінанта, перемикача, тега),
яке визначає, який з варіантів в даний
момент буде активізований. Значенням ознаки в кожний момент виконання програми повинна бути одна з розташованих далі
констант. Константа, слугує ознакою, задає варіант запису і називається
константою вибору. Наприклад, координати точки на площині, в залежності від системи координат , що використовується
(див. приклад 7.8), можна описати так
type CoordMode= (cart, polar);
Point= record
case Syst: CoordMode of
cart: (X, Y: real);
polar: (R, Phi: real)
end.
Правила використання записів з
варіантами:
·
всі
імена полів повинні відрізнятися одне
від одного якнайменше одним символом,
навіть якщо вони зустрічаються в
різних варіантах;
·
запис
може мати тільки одну варіантну частину, причому варіантна частина повинна розміщуватися в кінці запису;
·
якщо
поле, що відповідає якій-небудь константі аi, є порожнім,
то це записується таким чином: аi: ();
·
записи,
що містять варіантну частину, використовують в своєму описі тільки один ідентифікатор
end.
Приклад 3P. Відстань d між
двома точками а та b (задача 7.8):
program Distance;
type CoordMode= (cart,polar);
Point= record
case Syst: CoordMode of
cart: (X,Y: real);
polar: (R, Phi: real)
end;
var A, B: Point;
procedure Get_Point (var A: Point);
var S: byte;
begin
write('Система координат [1- прям, 2- поляр]?: ');
readln(S);
if S=1 then A.Syst:= cart else A.Syst:= polar;
write(' координати: ');
case A.Syst of
cart: readln(A.X,A.Y);
polar: readln(A.R,A.Phi)
end
end;
function Dist (A,B: Point): real;
begin
case A.Syst of
cart: case B.Syst of
cart: Dist:= sqrt(sqr(A.X-B.X)+
sqr(A.Y-B.Y));
polar: Dist:= sqrt(sqr(A.X-
B.R*cos(B.Phi))+sqr(A.Y-
B.R*sin(B.Phi)))
end;
polar: case B.Syst of
cart: Dist:= sqrt(sqr(A.R*cos(A.Phi)-
B.X)+sqr(A.R*sin(A.Phi)-B.Y));
polar: Dist:= sqrt(sqr(A.R)+sqr(B.R)-
2*A.R*B.R*cos(A.Phi-B.Phi))
end
end
end;
begin
writeln('Введення першої точки -');
Get_Point(A);
writeln('Введення другої точки -');
Get_Point(B);
writeln('Відстань між ними дорівнює ',Dist(A,B))
end.
У мові Сі записи називають структурами та описують так:
typedef struct {
t1 s1;
t2 s2;
...
tn sn;
} tr;
Приклади
описів даних типу запис:
typedef struct {
unsigned day;
enum {jan, feb, mar, apr, may, jun, jul,
aug, sep,
oct, nov, dec} month;
unsigned year;
} date;
typedef struct {
char nom[8]; (* номер *)
char marka[21]; (* марка автомобіля *)
unsigned color; (* колір автомобіля *)
char name[41]; (* П І Пб власника *)
char adress[61]; (* адреса власника *)
} avto;
date d;
avto m, v;
Доступ
до полів запису m: m.nom, m.marka, m.color, m.name, m.adress.
Виконувати присвоєння, введення-виведення
запису як агрегатного об'єкта -
заборонено. Дані дії виконуються для кожного поля
окремо.
Приклад 2C. Введення, виведення та додавання комплексних
чисел (задача 7.5).
#include <stdio.h>
#include <math.h>
/* COMPL */
typedef struct {
double re, im;
} complex;
get_c (complex *px)
{
printf("Дійсна частина числа=? "); scanf("%lf", &(*px).re);
printf("Уявна частина числа=? "); scanf("%lf", &(*px).im);
}
suma (complex x, complex y, complex *pz)
{
(*pz).re = x.re+y.re; (*pz).im = x.im+y.im;
}
put_c (complex x)
{
printf("%lf", x.re);
if (x.im>0) printf(" +"); else printf(" -");
printf("%lf * I\n", fabs(x.im));
}
main()
{
complex x,y,z;
printf("------ число X:\n"); get_c(&x);
printf("------ число Y:\n"); get_c(&y);
printf("Сума комплексних чисел дорівнює\n");
suma(x, y, &z); put_c(z);
}
Як і в
Паскалі для обчислення суми
використовується процедура, а не
програмована функція. Це пов'язано з тим,
що функція у Сі не може мати результат складеного типу (complex). Використання дужок у
позначеннях виду (*pz).re обумовлено тим, що
операція проекції (“.”) має більш високий пріоритет, ніж
розіменування вказівника (“*”).
Для
реалізації розмічених об’єднань у Сі використовують типи об’єднання (union). Опис типу об’єднання виглядає так:
typedef union {
t1 s1;
t2 s2;
...
tn sn;
} tu;
де tu – назва типу об’єднання, t1 , ..., tn - типи полів, s1, ..., sn – імена полів.
Об’єднання у Сі не мають поля дискримінанта,
отже не можна перевірити, до якого типу належить об’єднання у кожний момент
виконання програми. Відповідальність за слідкування за поточним типом
об’єднання (набором полів) покладається на програміста. Реалізувати тип
розміченого об’єднання з дискримінантом можна за допомогою комбінації типів
запису та об’єднання. Наприклад,
координати точки на площині, в
залежності від системи координат , що використовується (див. приклад 7.8), можна описати так
typedef enum {cart, polar} coord_mode;
typedef struct {
coord_mode cm;
union {
struct { double x, y;} с;
struct { double r, phi;} p;
} t;
} point;
point a, b;
Доступ до полів об’єднання виконується так само,
як і для записів, наприклад, a.cm, b.t.c.x, b.t.p.phi. Присвоєння, введення та виведення для об’єднань у Сі не визначені. Робота
з типами об’єднання здійснюється по окремих полях.
Приклад 3С. Відстань d між
двома точками а та b (задача 7.8):
#include <stdio.h>
#include <math.h>
/* Distance */
typedef enum {cart, polar} coord_mode;
typedef struct {
coord_mode cm;
union {
struct { double x, y;} c;
struct { double r, phi;}
p;
} t;
} point;
get_point (point *p)
{
int k;
printf("Система координат [1 - прям, 2 - поляр]: ");
scanf("%d",&k);
if (k==1)
{
(*p).cm = cart;
printf("Введіть x,y: ");
scanf("%lf %lf",&(*p).t.c.x,&(*p).t.c.y);
}
else
{
(*p).cm = polar;
printf("Введіть r,phi: ");
scanf("%lf %lf",&(*p).t.p.r,&(*p).t.p.phi);
}
}
double dist (point a, point b)
{
double d;
switch
(a.cm)
{
case
cart: switch (b.cm)
{
case cart: d = sqrt((a.t.c.x-b.t.c.x)*(a.t.c.x-b.t.c.x)+
(a.t.c.y-b.t.c.y)*(a.t.c.y-b.t.c.y));
break;
case polar: d = sqrt((a.t.c.x-b.t.p.r*cos(b.t.p.phi))*
(a.t.c.x-b.t.p.r*cos(b.t.p.phi))+
(a.t.c.y-b.t.p.r*sin(b.t.p.phi))*
(a.t.c.y-b.t.p.r*sin(b.t.p.phi)));
break;
}
break;
case
polar: switch (b.cm)
{
case cart: d = sqrt((a.t.p.r*cos(a.t.p.phi)-b.t.c.x)*
(a.t.p.r*cos(a.t.p.phi)-b.t.c.x)+
(a.t.p.r*sin(a.t.p.phi)-b.t.c.y)*
(a.t.p.r*sin(a.t.p.phi)-b.t.c.y));
break;
case polar: d = sqrt(a.t.p.r*a.t.p.r+b.t.p.r*b.t.p.r-
2*a.t.p.r*b.t.p.r*cos(a.t.p.phi-b.t.p.phi)
break;
}
break;
}
return d;
}
main()
{
point a,b;
printf("Введіть 2 точки \n");
get_point(&a);
get_point(&b);
printf("Відстань між ними дорівнює %lf \n",dist(a,b));
}