СТАТИЧНІ СТРУКТУРИ ДАНИХ R

ГЛАВА 3

 

СТАТИЧНІ СТРУКТУРИ ДАНИХ R

 

Поняття про дескриптор P

Вектори P

Масиви P

Множини P

Записи P

Таблиці P

 

СТАТИЧНІ СТРУКТУРИ ДАНИХ

 

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

 

Поняття про дескриптор

Статичні структури відносяться до розряду непримітивних структур, що представляють собою структуровану множину базових або інших інтегрованих… Кожну структуру даних будемо характеризувати її логічним і фізичним… Статичні структури в мовах програмування пов'язані із структурованими типами. До них відносять: вектори, масиви,…

Вектори

ЛОГІЧНА СТРУКТУРА. Вектор (одновимірний масив) – структура даних з фіксованим числом елементів однакового типу. Кожен елемент вектора має унікальний… МАШИННЕ ПРЕДСТАВЛЕННЯ. АДРЕСАЦІЯ ЕЛЕМЕНТІВ СТРУКТУР. Елементи вектора… У мовах програмування вектор представляється одновимірним масивом із синтаксисом опису вигляду (PASCAL):

Масиви

Логічна та фізична структури

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

Адресація елементів за допомогою векторів Айліффа

Для скорочення часу доступу до елементів масиву будь-якої розмірності формується набір дескрипторів: основного і декілька рівнів допоміжних…   Основний дескриптор Вектор Айліффа першого рівня

Множини

ЛОГІЧНА СТРУКТУРА. Множини – така структура, що представляє собою набір неповторюваних даних одного типу. Множини можуть приймати всі значення… ФІЗИЧНА СТРУКТУРА. Множина у пам'яті зберігається як масив бітів, у якому… Число байтів, виділених для даних типу множина, обчислюється за формулою:

Записи

 

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

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.

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

 

Таблиці

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

ВПРАВИ

1. Якою послідовністю команд в машині забезпечуються операції читання та запису елементів масиву?

2. Чи залежить час доступу до елементу масиву від його мірності?

3. Як можна скоротити час доступу до елемента масиву?

4. Чим визначається обсяг пам’яті, що необхідна для розміщення масиву?

5. Розробити структуру векторів Айліффа для звертання до елементів масиву М[-1..2, -5..-3, 3..5].

6. Чим відрізняється звертання до елемента масиву, як що він зберігається у стиснутому вигляді, у порівнянні із зберіганням його у повному обсязі?

7. Коли має сенс зберігати розріджені масиви з випадковим розташуванням елементів у стислому вигляді?

8. Покажіть, які переваги має нумерація елементів масиву, що починається від ”0” .

9. Чи можна під час виконання програми контролювати коректність звертання до полів записів з варіантами?

10. Який мінімальний і який максимальний обсяг пам’яті може бути виділено для змінної типу множина?

11. Чим відрізняється таблиця від масиву?

 

__________