конспект лекцій (ТСПП). Конспект лекцій з дисципліни 07 технологія створення програмних продуктів напряму 050101 Компютерні науки
 Скачать 14.87 Mb.
|
2.6. Прості структури даних.Структура і формат даних. Статичні, напівстатичні і динамічні структури На етапі визначення специфікацій для розробки якісного програмного забезпечення необхідно визначити структуру і формат використовуваних в програмах даних. Структура даних - це безліч елементів даних і зв'язків між ними. Незалежно від змісту і складності будь-які дані в пам'яті комп'ютера представляються у вигляді послідовності двійкових розрядів (бітів), а їх значеннями є відповідні двійкові числа. Бітові послідовності слабо структуровані і незручні для практичного застосування. На практиці зазвичай застосовують більше складно організовані структури даних. З поняттям структури даних тісно пов'язано поняття типу даних. Розрізняють фізичну і логічну структури даних. Фізична структура на відміну від логічної відбиває спосіб представлення даних в пам'яті комп'ютера і називається ще внутрішньою. По складу розрізняються прості структури (типи) даних і інтегрованих (складні). Прості структури не можуть бути розчленовані на складові частини, більші, ніж біти. З точки зору фізичної структури для простого типу чітко визначений його розмір і спосіб розміщення в пам'яті комп'ютера. З точки зору логічної структури прості структури є неділимими одиницями. Інтегровані структури даних включають інші структури даних - прості або інтегровані. Між окремими елементами структур можуть бути наявними або бути відсутнім явно задані зв'язки. Залежно від цього слід розрізняти: незв'язні структури (вектори, масиви, рядки, стеки, черги) і зв'язні структури (зв'язні списки). За ознакою мінливості розрізняють структури статичні, напівстатичні, динамічні. Під мінливістю розуміють зміну числа елементів структури або зв'язків між цими елементами. Класифікація структур даних за ознакою мінливості приведена на мал. 3.1. За ознакою впорядкованості елементів структури можна ділити на лінійні і нелінійні. Приклад нелінійних структур - багатозв'язкові списки, дерева, графи. Лінійні структури, у свою чергу, діляться на структури з послідовним розподілом (вектори, рядки, масиви, стеки, черги) і структури з довільним зв'язним розподілом (одинзв'язні, двозвязкові списки) по характеру розподілу елементів в пам'яті. Вказівка типу даних чітко визначає:
 Прості структури даних Прості структури даних служать основою для побудови складніших структур. Їх називають також примітивними або базовими структурами (типами даних). До них відносяться: числові, бітові, логічні, символьні, перераховувані, інтервальні, покажчики. Структура простих типів даних для мови Раscal приведена на мал. 3.2 (у інших мовах програмування набір і розміри простих типів можуть відрізнятися від приведеного на малюнку). Розмір кожного типу даних вказаний на малюнку в байтах через кому від назви типу. Як вже було сказано, різні типи даних мають різний формат представлення їх в машинній пам'яті. На мал. 3.3-3.5 наведені приклади форматів числових типів даних. На мал. 3.4 5 означає знаковий розряд числа (якщо S=0, то число позитивне, якщо S= 1 - число негативне). Формат для представлення чисел з плаваючою точкою, приведений на мал. 3.5, а, містить поля мантиси, порядку і знаків мантиси і порядку фіксованої довжини. Проте частіше замість порядку використовується характеристика, отримана шляхом збільшення до порядку зміщення, так щоб характеристика була завжди позитивною. При цьому має місце формат представлення дійсних чисел такий, як на мал. 3.5, би.  2.7. Статичні структури даних. Напівстатичні структури даних.Статичні структури даних Статичні структури є структурованою безліччю примітивних структур. Наприклад, вектор може бути представлений впорядкованою безліччю чисел. Мінливість невластива статичним структурам, т. е. розмір пам'яті комп'ютера, що відводиться для таких даних, постійний і виділяється на етапі компіляції або виконання програми. Вектори З логічної точки зору вектор (одновимірний масив) є структурою даних з фіксованим числом елементів одного і того ж типу. Кожен елемент вектору має свій унікальний номер (індекс). Звернення до елементу вектору виконується по імені вектору і номеру елементу. З фізичної точки зору елементи вектору розміщуються в пам'яті в підряд розташованих елементах пам'яті (мал. 3.6). Під елемент вектору виділяється кількість байт пам'яті, визначуване базовим типом елементу цього вектору. Тоді розмір пам'яті, що відводиться для розміщення вектору, визначатиметься наступним співвідношенням: S= до* Sizeof(тип), де до - кількість елементів (довжина) вектору, а Sizeof(тип) -- розмір пам'яті, необхідної для зберігання одного елементу вектору.  Мал. 3.6. Представлення вектору в пам'яті: @Ім'я - адреса вектору або адреса першого елементу вектору Двовимірні масиви Двовимірний масив (матриця) - це вектор, кожен елемент якого вектор. Тому те, що справедливо для вектору, справедливо і для матриці (аналогічно для n -мерных масивів). |