Як випливає з наведеного вище визначення, структурування даних передбачає існування (або встановлення) між ними якихось відносин (зв'язків). Залежно від характеру цих відносин можна виділити декілька класифікаційних ознак структур даних.
Першим з них розглянемо відношення порядку. Один по одному даних структури діляться на впорядковані і невпорядковані.
Прикладом невпорядкованих структур є, безлічі - в них не визначено порядок елементів; єдине, що можна встановити для якихось конкретних даних, так це їх приналежність (або не приналежність) обраному безлічі.
Наступним класифікаційним ознакою структур є однорідність. До однорідним відносяться структури, що містять елементарні дані тільки одного типу. Неоднорідні структури об'єднують дані різних типів. Прикладами однорідних структур є масиви, множини, стеки. До неоднорідним структурам називають протоколами.
Ще однією ознакою є характер відносин між елементами. За взаємною підпорядкованості елементів структури даних підрозділяються на лінійні і нелінійні.
У лінійних структурах все елементи рівноправні. До них відносяться масив, безліч, стек, чергу.
У нелінійних структурах між елементами існують відносини підпорядкованості або вони можуть бути пов'язані логічними умовами. До них відносяться дерева, графи, фрейми.
Грунтуючись на виділених класифікаційних ознаках, розглянемо і охарактеризуємо деякі структури даних.
Масив- упорядкована лінійна сукупність однорідних даних.
· Термін «упорядкована» означає, що елементи масиву пронумеровані;
· Термін «лінійна» свідчить про рівноправність всіх елементів;
· Термін «однорідних» означає наступне: в тому випадку, коли масив формується з елементарних даних, це можуть бути дані лише одного якогось типу, наприклад, масив чисел або масив символів; однак, не виключено, коли елементами масиву виявляться складні (структурні) дані, наприклад, масив масивів - в цьому випадку «однорідних» означає, що всі елементи мають однакову структуру і розмір.
Кількість індексів, що визначають положення елемента в масиві, називається мірність масиву.
Так, якщо індекс єдиний, масив називається одновимірним; часто такий масив називають також вектором, рядком або стовпцем. Для запису елементів одновимірного масиву використовується позначення mi; в мовах програмування прийняті позначення m (i) або m [i].
Масив, елементи якого мають два індекси, називається двовимірним або матрицею. Приклад позначення: G [3,5]; при цьому перший індекс є номером рядка, а другий індекс - номером стовпця, на перетині яких знаходиться даний елемент.
Масиви з трьома індексами називаються тривимірними і т.д. Максимальна мірність масиву може бути обмежена синтаксисом деяких мов програмування, або не мати таких обмежень.
Максимальне значення індексів визначає розмір масиву. Розмір масиву вказується в блоці опису програми, оскільки при виконанні програми для зберігання елементів масиву резервується необхідний обсяг пам'яті. Якщо в процесі виконання програми розмір масиву не змінюється (або не може бути змінений), то в цьому випадку говорять про масивах фіксованого розміру; якщо визначення розмірів масиву або їх зміна відбувається по ходу роботи програми, то такі масиви називаються динамічними (динамічно описаними).
Допустимий набір операцій над елементами масиву визначається типом даних (елементарних або структурованих), з яких масив сформований. У деяких мовах програмування над масивом в цілому визначена операція присвоювання М: = <выражение> - в цьому випадку всім елементам масиву присвоюється однакове значення, рівне обчисленому значенню виразу; можлива також операція присвоювання для двох однакових за типом, розміром і розмірності масивів М2: = М1 - проводиться поелементне присвоювання значень (M2 (i, j, k.): = M1 (i, j, k.)).
Особливе місце займають символьні масиви - вони називаються рядками або строковими даними (наприклад, тип String в PASCAL'e). З ними можливий цілий набір операцій, невизначених для одиночних символьних даних. В першу чергу, це операція конкатенації (об'єднання) рядків з формуванням нового рядка. До того ж є операції заміщення частини рядка, а також визначення її числових характеристик.
Відмінність черзі від стека тільки в тому, що вилучення інформації проводиться в порядку «першим увійшов - першим вийшов», тобто з дна стека.
Таким чином, дані мають порядок розташування і вони рівноправні - тому структура є впорядкованою і лінійної. Однак в загальному випадку в осередках стека можуть міститися дані різних типів - за цією ознакою структура виявляється неоднорідною.
Описаний спосіб організації даних виявляється зручним при роботі з підпрограмами, обслуговуванні переривань, вирішенні багатьох завдань.
Дерево або ієрархія є прикладом нелінійної структури. У ній елемент кожного рівня (за винятком самого верхнього) входить в один і тільки один елемент наступного (вищого) рівня. Елемент найвищого рівня називається коренем, а самого нижнього рівня - листям.
Схема такої структури показана на малюнку. Окремі елементи можуть бути однорідними чи ні. Прикладом подібної організації служать файлові структури на зовнішніх запам'ятовуючих пристроях комп'ютера.
Часто відносини між даними представляються у вигляді графа - сукупності точок і ліній, в якій кожна лінія з'єднує дві точки. В інформатиці точка отримує сенс елемента структури (системи, даних і ін.), А лінії - сенс відносини між елементами. Познайомимося з рядом термінів, пов'язаних з використанням графів.
Точки називаються вершинами графа, лінії - ребрами. Якщо ребро з'єднує дві вершини, то говорять, що ребро інцидентне цих вершин, а самі вершини називаються суміжними. Число ребер, інцидентних вершині, називається ступенем вершини. Якщо два ребра інцидентні одній і тій же парі вершин, вони називаються кратними. Ребро, у якого збігаються обидві вершини, називається петлею.
На рис. 6.3, а. граф 1 задається списком вершин і списком ребер, в якому для кожного ребра вказується пара інцідентних йому вершин: а (1,2); b (1,4); з (2, .4); 6 (2,3); е (3,4); f (2,3); g (4,4).
Суміжні пари вершин: (2,3), (2,4), (1,2), (1,4), (3,4). Ребро д є петлею; ребра d і f - кратні. Ступені вершин 2 і 4 рівні 4; вершини 3 -3; вершини 1 - 2.
Ребро, що з'єднують вершини, може мати направлення - тоді воно називається орієнтованим і зображується стрілкою. Граф, в якому все ребра орієнтовані, називається орієнтованим; його ребра часто називають дугами. Дуги називають кратними, якщо вони з'єднують одні і ті ж вершини і збігаються за напрямком. При позначенні дуги завжди спочатку вказується вершина, з якої вона починається, наприклад, на рис. 6.3, б (2,3).
Маршрут - це послідовність ребер, в якому кінець попереднього ребра збігається з початком наступного, наприклад, а. с, е на графі 1. Маршрут, в якому кінцева вершина збігається з початковою, називається циклом, наприклад, с. е, d на графі 2. Граф називається зв'язковим, якщо між будь-якими двома його вершинами є маршрут. Зв'язний граф з п вершинами містить не менше п -1 ребер.
За розглянутої раніше класифікації граф є впорядкованою, нелінійної, неоднорідною структурою. Поняття графа завдяки його наочності та високою спільності в інформатиці виступає в якості основного засобу опису структур даних, систем, порядку виконання дій. Прикладом може служити блок-схема програми.
З точки зору практичного використання вельми цікавим є ще один тип даних, що утворюють впорядковану, лінійну, неоднорідними структуру. Таку структуру можна розглядати як масив неоднорідних структурованих даних.
Структура називається таблицею, а її окремий рядок - записом (логічної записом). З огляду на велику значущість даної структури вона буде розглянута більш докладно.
Повернутися в зміст: Теоретичні основи інформатики