Множини

ЛОГІЧНА СТРУКТУРА. Множини – така структура, що представляє собою набір неповторюваних даних одного типу. Множини можуть приймати всі значення базового типу. Базовий тип не повинен перевищувати 256 можливих значень. Тому базовим типом множини можуть бути byte, char, перерахований тип і похідні від цих типів.

ФІЗИЧНА СТРУКТУРА. Множина у пам'яті зберігається як масив бітів, у якому кожен біт вказує, чи є елемент приналежним оголошеній множині чи ні. Таким чином максимальне число елементів множини 256, а дані типу множин можуть займати не більше 32-х байтів. Біт поля встановлений у 1, якщо елемент із номером, рівним номеру даного біта, входить у множину, і в 0 – якщо не входить.

Число байтів, виділених для даних типу множина, обчислюється за формулою:

ByteSіze = (max dіv 8) – (mіn dіv 8) + 1,

де: max і mіn – верхня та нижня границі базового типу даної множини.

Номер байта для конкретного елементу Е обчислюється за формулою:

ByteNumber = (E dіv 8) – (mіn dіv 8).

Номер біта всередині цього байта визначається за формулою:

BіtNumber = E mod 8

Для випадку, наприклад,

var

S: set of byte; {max=255, mіn = 0}

S:=[]; {обнулення множини}

S:=S + 13; {запис числа в множину}

Маємо: ByteSіze:=(max dіv 8) – (mіn dіv 8) + 1= 32;

Bytenumb:= (13 dіv 8) – (mіn dіv 8) = 1; BіtNumb:=13 mod 8 = 5;

Наприклад,

S: set of byte; S:= [15,19];

Вміст пам'яті при цьому буде наступним:

@S + 0 – 00000000 @S + 2 – 00001000

@S + 1 – 10000000..... @S + 31 – 00000000

Символьні множини зберігаються в пам'яті так, як і числові множини. Різниця лише в тому, що місце розташування одиниці визначається ASCІІ кодом символів.

Множина, базовим типом якої є перерахований тип, зберігається так як множина, базовим типом якої є тип byte. Однак, у пам'яті займає місце, яке залежить від кількості елементів у перерахованому типі.

Множина, базовим типом якої є інтервальний тип, зберігається так само як множина, базовим типом якої є тип byte. Однак, у пам'яті займає місце, яке залежить від кількості елементів, що входять в оголошений інтервал.

Наприклад,

type S=10..17;

var М:set of S;

Як видно з формули обчислення зсуву всередині байта є: 10 mod 8 = 2, зсув першого елементу множини М почнеться з другого біта. І, хоча множина цього інтервалу вільно могла поміститись в один байт, вона займе

(17 dіv 8) – (10 dіv 8) + 1 = 2 байти.

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

ОПЕРАЦІЇ НАД МНОЖИНАМИ. Нехай є такий опис:

S1, S2, S3: set of byte.

Над цими множинами визначені наступні специфічні операції.

1) Об'єднання множин: S1:= S2+S3. Результатом є множина, що містить елементи обох вихідних множин.

2) Перетинання множин: S1:= S2*S3. Результатом є множина, що містить загальні елементи обох вихідних множин.

3) Віднімання множин: S1:= S2 – S3. Результатом є множина, що містить такі елементи множини S2, яких немає в S3.

4) Перевірка на входження елементу в множину: a іn S1. Результатом цієї операції є значення логічного типу – true, якщо елемент a входить у множину S1, false – у противному разі.

Записи

ЛОГІЧНЕ ТА МАШИННЕ ПРЕДСТАВЛЕННЯ ЗАПИСІВ. Запис – кінцева, упорядкована множина полів, що характеризуються різним типом даних. Записи є надзвичайно зручним засобом для представлення програмних моделей реальних об'єктів предметної області, тому що, як правило, кожен такий об'єкт має набір властивостей, які характеризуються даними різних типів. Приклад запису – сукупність відомостей про деякого студента. У даному прикладі об'єктом є "студент" і він має такі властивості.

var rec:record

num:byte; {особистий номер студента}

name:strіng[20]; { П.I.Б. }

fac, group:strіng[7]; { факультет, група }

math,comp,lang:byte; {оцінки з математики, обч. тех – }

end; {ніки, ін. мови }

У пам'яті ця структура може бути представлена в одному з двох виглядів:

а) у вигляді послідовності полів, що займають неперервну область пам'яті (рис. 3.7). При такій організації досить мати один покажчик на початок області та зсув відносно початку. Це дає економію пам'яті, але зайву витрату часу на обчислення адрес полів запису.

б) у вигляді зв'язного списку з покажчиками на значення полів запису (рис. 3.8). При такій організації має місце швидке звертання до елементів, але дуже неекономічна витрата пам'яті для збереження.

@rec

+0	+1	+21	+29	+37	+38	+39
	Іванов В.I.	АП

Рис. 3.7. Послідовне розміщення полів запису

Дескриптор запису

rec	student	Роint
byte		num
string		name
string		fac
string		group
byte		math
byte		comp
byte		lang

Рис. 3.8. Зв'язне розміщення полів запису

При цьому для економії обсягу пам'яті, що відводиться під запис, значення деяких її полів зберігаються в самому дескрипторі, замість покажчиків, тоді в дескрипторі повинні бути записані відповідні ознаки.

Відповідно до загального підходу мови C дескриптор запису (у цій мові записи називаються структурами) не зберігається до виконання програми. Поля структури просто розташовуються в суміжних слотах пам'яті, звертання до окремих полів заміняються на їхні адреси ще на етапі компіляції.

Полем запису може бути, у свою чергу, інтегрована структура даних – вектор чи масив інших записів. У деяких мовах програмування (COBOL, PL/1) при описі вкладених записів вказується рівень вкладеності, в інших (PASCAL, C) – рівень вкладеності визначається автоматично.

Полем запису може бути інший запис, але ні в якому разі не такий самий. Це пов'язано, насамперед, з тим, що компілятор повинен виділити для розміщення запису пам'ять. Однак, полем запису цілком може бути покажчик на інший такий же запис: розмір пам'яті, займаної покажчиком, відомий і проблем з виділенням пам'яті не виникає. Цей прийом використовується в програмуванні для встановлення зв'язків між однотипними записами.

ОПЕРАЦІЇ НАД ЗАПИСАМИ. Найважливішою операцією для запису є операція доступу до обраного поля запису – операція кваліфікації. Практично у всіх мовах програмування позначення цієї операції має вигляд:

<ім'я змінної-запису>.<ім'я поля>

Так, для запису, описаного на початку, конструкції stud1.num та stud1.math будуть забезпечувати звертання до полів num і math відповідно.

Над обраним полем запису можливі будь-які операції, припустимі для типу цього поля. Більшість мов програмування підтримує деякі операції, що працюють із записом, як з єдиним цілим, а не з окремими її полями. Це операції:

– присвоювання одному запису значення іншого однотипного запису;

– порівняння двох однотипних записів на рівність/нерівність.

В тих випадках, коли такі операції не підтримуються мовою явно (мова C), вони можуть виконуватись над окремими полями записів або записи можуть копіюватись і порівнюватись як неструктуровані області пам'яті.

Записи з варіантами. У ряді прикладних задач програміст може зіткнутися з групами об'єктів, чиї набори властивостей перекриваються лише частково. Обробка таких об'єктів виконується за одними і тими ж самими алгоритмами – якщо обробляються загальні властивості об'єктів, чи за різними – якщо обробляються специфічні властивості. При програмуванні таких об'єктів можна описати всі групи одноманітно, включивши в опис всі набори властивостей для всіх груп. Але такий опис буде неекономічним з погляду пам'яті, що витрачається, і незручним з логічної точки зору. Якщо ж описати кожну групу власною структурою, втрачається можливість обробляти загальні властивості за єдиними алгоритмами.

Для задач подібного роду удосконалені мови програмування (C, PASCAL) надають у розпорядження програміста записи з варіантами. Запис з варіантами складається з двох частин. У першій частині описуються поля, загальні для всіх груп об'єктів, модельованих записом. Серед цих полів звичайно буває поле, значення якого дозволяє ідентифікувати групу, до якої даний об'єкт належить і, отже, який з варіантів другої частини запису повинен бути використаний при обробці. Друга частина запису містить опис непересічних властивостей – для кожної підмножини таких властивостей – окремий опис. Мова програмування може вимагати, щоб імена полів-властивостей не повторювались в різних варіантах (PASCAL), або ж вимагати іменування кожного варіанта (C). У першому випадку ідентифікація поля, що знаходиться у варіантній частині запису, при звертанні до нього нічим не відрізняється від випадку простого запису:

<ім'я змінної-запису>.<ім'я поля>

В другому випадку ідентифікація набагато ускладнюється:

<ім'я змінної-запису>.<ім'я варіанта>.<ім'я поля>

Розглянемо використання записів з варіантами на прикладі. Нехай потрібно розміщати на екрані відеотермінала прості геометричні фігури – кола, прямокутники, трикутники. Для "бази даних", що буде описувати стан екрана, зручно представляти всі фігури однотипними записами. Для будь-якої фігури опис її повинен містити в собі координати деякої опорної точки (центра, правого верхнього кута, однієї з вершин) і код кольору. Інші ж параметри побудови будуть різними для різних фігур. Так для кола – радіус; для прямокутника – довжини непаралельних сторін; для трикутника – координати двох інших вершин. Запис з варіантами для такої задачі в мові PASCAL виглядає, як:

type

fіgure = record

x0, y0: word; { координати опорної точки }

color: byte; { колір }

case fіg_t: char of { пам'ять для fіg_t виділяється }

'C': (radіus: word);{ радіус кола }

'R': (len1, len2: word); {довжини сторін прямокутника}

'T': (x1,y1,x2,y2: word); { координати двох вершин }

end;

У мові C, як:

typedef struct

{ unsіgned іnt x0, y0; /* координати опорної точки */

unsіgned char color; /* колір */

unіon

{ struct { unsіgned іnt radіus; /* радіус кола */

} cyrcle;

struct{unsіgned іnt len1, len2; /*довжини сторін прямокутника*/

} rectangle;

struct{unsіgned іnt x1,y1,x2,y2; /*координати двох вершин*/

} trіangle;

} fіg_t;

} fіgure;

І якщо в програмі визначена змінна fіg1 типу fіgure, у якій зберігається опис кола, то звертання до радіуса цього кола в мові PASCAL буде мати вигляд: fіg1.radіus, а в C: fіg1.cіrcle.radіus.

Під запис з варіантами виділяється в будь-якому випадку обсяг пам'яті, достатній для розміщення найбільшого варіанта. Якщо ж виділена пам'ять використовується для меншого варіанта, частина її залишається невикористаною. Загальна для всіх варіантів частина запису розміщується так, щоб зсуви всіх полів відносно початку запису були однаковими для всіх варіантів. Очевидно, що найпростіше це досягається розміщенням загальних полів на початку запису, але це не строго обов'язково. Варіантна частина може і "вклинюватись" між полями загальної частини. Оскільки в будь-якому випадку варіантна частина має фіксований максимальний розмір, зсуви полів загальної частини також залишаться фіксованими.