Ієрархічні структури даних

Таблиці даних, матриці даних

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

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

ялині потрібно зберегти таблицю у вигляді довгого символьного рядка, використовують один символ - роздільник між елементами, що належать одному рядку, і інший роздільник для відділення рядків, наприклад так:

Меркурий*0,39*0,056*0#Венера*0,67*0,88*0#Земля*1,0*1,0*1#Марс*1,51*0,1*2#...

Для розшуку елементу, що має адресу осередку (т, п), треба проглянути набір даних Із самого початку і перерахувати зовнішні роздільники. Коли буде відлічений т-1 роздільник, треба перераховувати внутрішні роздільники. Після того, як буде знайдений n-1 роздільник, почнеться потрібний елемент. Він закінчиться, коли буде зустрінутий будь-який черговий роздільник.

Ще простіше можна діяти, якщо всі елементи таблиці мають рівну довжину. Такі таблиці називають матрицями. В даному випадку роздільники не потрібні, оскільки всі елементи мають рівну довжину і кількість їх відомо. Для розшуку елементу з адресою (т, п) в матриці, що має М рядків і N стовпців, треба про­смотреть її із самого початку і відлічити а[N (т-1) + (п-1)] символ, де а — довжина одного елементу. З наступного символу почнеться потрібний елемент. Його довжина теж рівна а, тому його кінець визначити неважко.

Таким чином, табличні структури даних (матриці) — це впорядковані структури, в яких адреса елементу визначається номером рядка і номером стовпця, на перетині яких знаходиться осередок, що містить шуканий елемент.

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

Номер факультету: 3

Номер курсу (на факультеті): 2

Номер спеціальності (на курсі): 2

Номер групи в потоці однієї спеціальності: 1

Номер що вчиться в групі: 19

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

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

У ієрархічній структурі адреса кожного елементу визначається шляхом доступу маршрутом, ведучим від вершини структури до даного елементу. Ось, наприклад, як виглядає шлях доступу до команди, що запускає програму Калькулятор (стандартна програма комп'ютерів, що працюють в операційній системі Windows 98): Пуск > Програми > Стандартні > Калькулятор.

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

У ієрархічній структурі, побудованій методом дихотомії, шлях доступу до будь-якого лементу можна представити як шлях через раціональний лабіринт з поворотами наліво (0) або направо (1) і, таким чином, виразити шлях доступу у вигляді компактного двійкового запису. У нашому прикладі шлях доступу до текстового процесора Word 2000 виразиться наступним двійковим числом 1010.