Модульне програмування

Записи

Запис – це комбінований тип, значення якого представляють собою нетривіальну структуру даних. Вони складаються з декількох полів різного типу, доступ до яких здійснюється по їх іменам. Записи представляють собою засіб для представлення програмних моделей реальних об’єктів предметної області, так як кожен такий об’єкт володіє декількома властивостями, які можуть описуватись даними різних типів.

Приклад запису – набір даних про співробітника кафедри.

Об’єкт «співробітник» може володіти наступними властивостями:

– табельний номер – ціле додатне число;

– прізвище, ім’я, по-батькові – рядок символів і т.д.;

– стать – символ;

– вчена ступінь – рядок символів;

– заробітна плата – дійсне число;

– ти ін.

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

– у вигляді послідовності полів, які займають неперервну область пам’яті (рис. 3.8). Щоб отримати доступ до будь якого елемента запису, потрібно знати адресу початку запису і зміщення відносно початку. При цьому досягається економія пам’яті комп’ютера, але затрачується зайвий час на обчислення адрес полів;

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

3.3.4. Напівстатичні структури даних

Властивості напівстатичних структур даних:

– вони мають змінну довжину і прості способи її зміни;

– зміна довжини структури відбувається у визначених межах, не перевищуючи деякого максимального (граничного) значення.

З логічної точки зору напістатична структура представляє собою послідовність даних, зв’язану відношеннями лінійного списку (див. розділ 3.3.5). Доступ до елемента може здійснюватись по його порядковому номеру.

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

До напівстатичних структур належать стеки, черги, деки, строки.

3.3.5. Динамічні структури даних

Динамічні структури не мають постійного розміру, тому пам’ять під окремі елементи таких структур виділяється в момент, коли вони створюються в процесі виконання програми, а не під час трансляції. Коли в елементі структури більше немає необхідності, пам’ять звільняється (елемент «руйнується»).

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

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

З допомогою зв’язного представлення даних забезпечується висока мінливість структури. Переваги динамічних структур:

– розмір структури обмежується тільки об’ємом пам’яті комп’ютера;

– при зміні логічної послідовності елементів структури (видалення, додавання елемента, зміна порядку розміщення елементів) вимагається тільки корекція вказівників.

З іншого боку, такі структури володіють ряд недоліків:

– робота з вказівниками вимагає високої кваліфікації програміста;

– на вказівники витрачається додаткова пам’ять;

– додаткова трата часу на доступ до елементів зв’язної структури.

Зв’язні лінійні списки

Лінійні зв’язні списки є найпростішими динамічними структурами даних. Вони є впорядкованими множинами, які містять змінне число елементів, на які не накладаються обмеження по довжині.

На рис. 3.10 приведена структура однозв’язного списку. Тут поле INF – інформаційне поле, яке містить дані, NEXT – вказівник на наступний елемент списку. Голова списку – вказівник на початок списку. Вказівник на наступний елемент останнього елемента містить значення nil, це є ознакою останнього елемента.

Двозв’язні списки

Обробка однозв’язного списку не завжди зручна, так як неможливо рухатись в протилежну сторону. Таку можливість забезпечує двозв’язний список, кожен елемент якого містить два вказівника: на наступний і попередній елементи. Структура лінійного двозв’язного списку на рис 3.11, де поле NEXT – вказівник на наступний елемент, PREV – вказівник на попередній елемент. Перший і останній елементи такого списку містять nil у вказівнику на попередній і наступний елементи відповідно.

Для зручності обробки списку додають ще один особливий елемент – вказівник кінця списку. Наявність двох вказівників в кожному елементі ускладнює список і призводить до додаткових затрат пам’яті, але в той же час забезпечує більш ефективне виконання деяких операцій над списком.

Для забезпечення технологічності розроблюваного програмного забезпечення використовується модульне програмування.

Дата добавления: 2014-01-04