Алгоритми і структури даних Опорний конспект лекцій для студентів заочно-дистанційної форми навчання спеціальності „Економічна кібернетика”



Сторінка2/19
Дата конвертації20.11.2016
Розмір1.02 Mb.
1   2   3   4   5   6   7   8   9   ...   19

1.2.Концепція структур даних


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

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

Структура даних відноситься за своєю суттю до „просторових” понять: її можна звести до схеми організації інформації в пам’яті комп’ютера. Алгоритм ж є відповідним процедурним елементом в структурі програми – він служить рецептом розрахунку.

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

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

Поняття „фізична структура даних” відображає спосіб фізичного представлення даних в пам’яті машини і називається ще структурою зберігання.

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

Розгляд структур даних утруднений досить незручним змішуванням абстрактних властивостей структур даних і проблемами представлення, які зв’язані з комп’ютером і машинною мовою. Важливо чітко розрізняти ці проблеми за допомогою багаторівневого опису. Будь-яка структура даних може описуватися, таким чином, на трьох різних рівнях:



  • Функціональна специфікація – вказує для деякого класу імен операції, які дозволені з цими іменами, і властивості цих операцій;

  • Логічний опис – задає декомпозицію об’єктів на більш елементарні об’єкти і декомпозицію відповідних операцій на більш елементарні операції;

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

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

1.3.Класифікація структур даних


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

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



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

У залежності від наявності чи відсутності явно заданих зв’язків між елементами даних потрібно розрізняти незв’язні структури і зв’язні структури.

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

Ще одна важлива ознака структури даних – характер впорядкованості її елементів. За цією ознакою структури можна поділити на лінійні й нелінійні структури.


1.4.Операції над структурами даних


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

Операція створення полягає у виділенні пам’яті для зберігання структури даних. Пам’ять може виділятися в процесі виконання програми або на етапі компіляції. У деяких мовах для структурованих даних, які конструюються програмістом, операція створення включає в себе також встановлення початкових значень параметрів, створюваної структури (ініціалізація).

Незалежно від використовуваної мови програмування, наявні в програмі структури даних не появляються „з нічого”, а явно або неявно оголошуються операторами створення.

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

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

Операція поновлення дозволяє змінити значення даних в структурі даних. Прикладом операції поновлення є операція присвоєння, або, більш складна форма – передача параметрів.

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

1   2   3   4   5   6   7   8   9   ...   19


База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

    Головна сторінка