Прості структури даних

Структура і формат даних. Статичні, напівстатичні і динамічні структури

На етапі визначення специфікацій для розробки якісного програмного забезпечення необхідно визначити структуру і формат використовуваних в програмах даних.

Структура даних - це безліч елементів даних і зв'язків між ними.

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

З поняттям структури даних тісно пов'язано поняття типу даних.

Розрізняють фізичну і логічну структури даних. Фізична структура на відміну від логічної відбиває спосіб представлення даних в пам'яті комп'ютера і називається ще внутрішньою.

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

Між окремими елементами структур можуть бути наявними або бути відсутнім явно задані зв'язки. Залежно від цього слід розрізняти: незв'язні структури (вектори, масиви, рядки, стеки, черги) і зв'язні структури (зв'язні списки).

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

За ознакою впорядкованості елементів структури можна ділити на лінійні і нелінійні. Приклад нелінійних структур - багатозв'язкові списки, дерева, графи.

Лінійні структури, у свою чергу, діляться на структури з послідовним розподілом (вектори, рядки, масиви, стеки, черги) і структури з довільним зв'язним розподілом (одинзв'язні, двозвязкові списки) по характеру розподілу елементів в пам'яті.

Вказівка типу даних чітко визначає:

• розмір пам'яті, відведеної під цю структуру і спосіб її розміщення в пам'яті;

• значення, допустимі для цього типу даних;

• операції, які можливо над цими даними виконувати.

Прості структури даних

Прості структури даних служать основою для побудови складніших структур. Їх називають також примітивними або базовими структурами (типами даних). До них відносяться: числові, бітові, логічні, символьні, перераховувані, інтервальні, покажчики. Структура простих типів даних для мови Раscal приведена на мал. 3.2 (у інших мовах програмування набір і розміри простих типів можуть відрізнятися від приведеного на малюнку). Розмір кожного типу даних вказаний на малюнку в байтах через кому від назви типу.

Як вже було сказано, різні типи даних мають різний формат представлення їх в машинній пам'яті.

На мал. 3.3-3.5 наведені приклади форматів числових типів даних.

На мал. 3.4 5 означає знаковий розряд числа (якщо S=0, то число позитивне, якщо S= 1 - число негативне).

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

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