Ієрархічні структури даних
Дерево - динамічна ієрархічна структура даних, представлена єдиним кореневим вузлом і його нащадками. Максимальна кількість нащадків кожного вузла визначає розмірність (ступінь) дерева.
Виділяють виконавчі або бінарні дерева, оскільки вони використовуються в алгоритмах сортування і пошуку. Кожен вузол двійкового дерева пошуку відповідає елементу з деякого відсортованого набору. Всі його «ліві» нащадки є меншими елементами, а «праві» - великими. Кожен вузол в дереві однозначно ідентифікується послідовністю неповторяющихся вузлів від кореня і до нього, яку називають шляхом.
Довжина шляху є рівнем вузла в ієрархії дерева. Для двійкових або бінарних дерев виділяють наступні види рекурсивного обходу всіх його елементів (в фігурних дужках вказано порядок відвідування елементів кожного вузла, починаючи з кореня):
Щоб вивести елементи в порядку їх зростання, дерево пошуку обходять в симетричному порядку. Для виведення в зворотному порядку в процесі обходу необхідно поміняти порядок відвідування піддерев.
Двійкове (бінарне) дерево.
Ієрархічний список являє собою комбінацію лінійного списку і дерева. Кожен елемент такого списку може бути початком списку наступного підрівні ієрархії. Приклад ієрархічного списку - структура інтернет форумів: послідовність повідомлень утворює лінійний список, в той час як повідомлення, що є відповідями на інші повідомлення, породжують нові потоки обговорення.
Мережеві структури даних
Елемент в мережевій структурі характеризується набором зв'язків з іншими - сусідніми елементами. У таких структурах ні початковий, ні кореневої елементи явно не виділені.
Граф - динамічна мережева структура даних, представлена набором вершин і ребер - зв'язків між вершинами. Кожна вершина може бути пов'язана з будь-яким числом інших вершин або з самою собою. У графі немає ніякої чіткої ієрархії. Якщо розглядати вузли дерева, як вершини, а зв'язки між вузлами дерева різних рівнів ієрархії, як ребра, то саме дерево можна вважати графом, що не містить циклів або ациклічним графом.
Якщо для кожного ребра графа визначено напрямок, то це орієнтований граф. Крім напрямки кожне ребро графа може мати свою вагу. За допомогою графа, наприклад, моделюються транспортні мережі і вирішуються завдання на оптимізацію транспортних потоків. Завантаженість або, навпаки, пропускна здатність транспортних магістралей задається вагою відповідних ребер.
4. Табличні структури даних
Елемент в табличній структурі даних характеризується двома індексами: рядки і стовпці, на перетині яких він знаходиться. Прикладами табличних структур даних є двовимірні масиви і таблиці реляційної бази даних.
Табличні структури даних.
Взагалі, файл - це динамічна структура даних, розмір якої може змінюватися в процесі виконання програми (його розмір може бути дорівнює нулю, що відповідає пустому файлу). У кожен момент часу може бути доступний тільки один елемент файлу. Існує кілька видів файлів: текстові, типізовані і ін.
Складність типових операцій при роботі
з лінійними структурами даних