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

Класифікація структур даних виконується за декількома ознаками.

1). За способом представлення: фізична та логічна.

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

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

2). За складністю: прості й інтегровані.

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

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

3). За наявністю зв'язківміж елементами даних: незв'язні та зв'язні.

Незв'язні структури характеризуються відсутністю зв'язків між елементами структури, зв'язні – наявністю такого зв'язку. Прикладами незв'язних структур є вектори, масиви, рядки, стеки, черги; приклади зв'язних структур – зв'язні списки.

4). За мінливістю: статичні, напівстатичні, динамічні.

Дуже важлива ознака структури даних - її мінливість, тобто зміна числа елементів і (чи) зв'язків між елементами структури. У визначенні мінливості структури не відбитий факт зміни значень елементів даних, оскільки в цьому випадку всі структури даних мали б властивість мінливості.

Статичні – до цієї групи відносять масиви, множини, записи, таблиці.

Напівстатичні – це стеки, черги, деки, дерева.

Динамічні – лінійні та розгалужені зв'язні списки, графи, дерева.

5). За характером упорядкованості елементів у структурі: лінійні та нелінійні.

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

Нелінійні структури – багатозв¢язні списки, дерева, графи.

6). За видом пам'яті, використовуваної для збереження даних: структури даних для оперативної і для зовнішньої пам'яті.

Структури даних для оперативної пам'яті – це дані, розміщені в статичній і динамічній пам'яті комп'ютера. Всі вищенаведені структури даних – це структури для оперативної пам'яті.

Структури даних для зовнішньої пам'яті називають файловими структурами чи файлами. Прикладами файлових структур є послідовні файли, файли, організовані розділами, В-дерева.

У мовах програмування поняття "структури даних" тісно пов'язано з поняттям "типи даних". Будь-які дані, тобто константи, змінні, значення функції чи виразу, характеризуються своїми типами. Інформація для кожного типу однозначно визначає:

а) структуру збереження даних зазначеного типу, тобто розподіл пам'яті та представлення даних у ній, з одного боку, та інтерпретування двійкового представлення, з іншого;

б) припустимі значення, що може мати об'єкт описуваного типу;

в) припустимі операції, що можуть бути застосовні до об'єкта описуваного типу.