Ієрархічні структури даних
Нерегулярні дані, які важко представити у вигляді списку чи таблиці, часто представляють у вигляді ієрархічних структур. З подібними структурами ми дуже добре знайомі по повсякденному життю. Ієрархічну структуру має система поштових адрес. Подібні структури також широко застосовуються у наукових систематизаціях і всіляких класифікаціях (мал. 1.5).
В ієрархічній структурі адреса кожного елемента визначається шляхом доступу (маршрутом), що веде від вершини структури до даного елемента. От, наприклад, як виглядає шлях доступу до команди, що запускає програму Калькулятор (стандартна програма комп'ютерів, що працює в операційній системі Windows 98):
Пуск > Программы > Стандартные > Калькулятор.
Дихотомія даних. Основним недоліком ієрархічних структур даних є збільшений розмір шляху доступу. Дуже часто буває так, що довжина маршруту виявляється більшою, ніж довжина самих даних, до яких він веде. Тому в інформатиці застосовують методи для регуляризації ієрархічних структур для того, щоб зробити шлях доступу компактним. Один з методів одержав назву дихотомії. Його суть зрозуміла з прикладу, представленого на мал. 1.6.
В ієрархічній структурі, побудованій методом дихотомії, шлях доступу до будь-якого елемента можна представити як шлях через раціональний лабіринт із поворотами ліворуч (0) чи праворуч (1) і, таким чином, виразити шлях доступу у вигляді компактного двійкового запису. У нашому прикладі шлях доступу до текстового процесора Word 2000 виразиться наступним двійковим числом: 1010.
2.9. Упорядкування структур даних
Лінійні й табличні структури є простими. Ними легко користуватися, оскільки адреса кожного елемента задається числом (для списку), двома числами (для двовимірної таблиці) чи декількома числами для багатомірної таблиці. Вони також легко упорядковуються. Основним методом упорядкування є сортування. Дані можна сортувати по будь-якому обраному критерію, наприклад: за алфавітом, по зростанню порядкового номера чи по зростанню якого-небудь параметра.
Незважаючи на численні зручності, у простих структур даних є і недолік — їх важко обновляти. Якщо, наприклад, перевести студента з однієї групи в іншу, зміни треба вносити відразу в два журнали відвідування; при цьому в обох журналах буде порушена облікова структура. Якщо переведеного студента вписати в кінець списку групи, порушиться упорядкування за алфавітом, а якщо його вписати відповідно до алфавіту, то зміняться порядкові номери всіх студентів, що розміщені за ним. Таким чином, при додаванні довільного елемента в упорядковану структуру списку може відбуватися зміна адресних даних у інших елементів.
У журналах успішності це виправити неважко, але в системах, що виконують автоматичну обробку даних, потрібні спеціальні методи для вирішення цієї проблеми.
Ієрархічні структури даних за формою складніші, ніж лінійні і табличні, але вони не створюють проблем з відновленням даних. Їх легко розвивати шляхом створення нових рівнів. Навіть якщо в навчальному закладі буде створений новий факультет, це ніяк не відіб'ється на шляху доступу до інформації про інших студентів, що навчаються на факультеті.
Недоліком ієрархічних структур є відносна трудомісткість запису адреси елемента даних і складність упорядкування. Часто методи упорядкування в таких структурах засновують на попередній індексації, що полягає в тому, що кожному елементу даних привласнюється свій унікальний індекс, який можна використовувати при пошуку, сортуванні і т.п. Раніше розглянутий принцип дихотомії насправді є одним з методів індексації даних в ієрархічних структурах. Після такої індексації дані легко знаходяться по двійковому коду, зв'язаного з ними по індексу.
Адресні дані. Якщо дані зберігаються не хаотично, а в організованій структурі, то кожен елемент даних здобуває нову властивість (параметр), який можна назвати адресою. Звичайно, працювати з упорядкованими даними зручніше, але за це необхідно платити їх розмноженням, оскільки адреси елементів даних — це теж дані, і їх теж треба зберігати й обробляти.