Структури даних, Детальна інформація

Якщо ключі не унікальні, то можна утворити m списків, кожен з який містить елементи з однаковими ключами. Час пошуку елемента із заданим ключем залишається рівним O(1). Але якщо елементи з одного списку мають різні характеристики (незважаючи на спільний ключ), і кількість елементів у списку дорівнює d, то час пошуку такого елемента складатиме O(d).

Система неперитинаючих множин – це набір непорожніх множин, які не перетинаються, в кожній з яких зафіксовано один із елементів (представник). На системі неперетинаючих множин підтримуються наступні операції:

Make-Set (x). Утворення множини. Процедурі передається вказівник на вже існуючий об’єкт х. Процедура утворює нову множину, єдиний елемент якої задається вказівником х. Оскільки множини не повинні перетинатися, елемент х повинен вказувати на новий об’єкт (який не лежить в жодній із існуючих множин).

Find-Set (x). Знайти множину. Повертає вказівник на представника (єдиного) множини, який містить елемент, на який вказує х.

Union (x, y). Об’єднання. Процедура застосовується, якщо елементи x та y містяться у різних множинах Sx та Sy і замінює ці множини на об’єднання Sx \xF0C8 Sy; при цьому обирається деякий представник для Sx \xF0C8 Sy. Самі множини Sx та Sy при цьому знищуються.

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

При такій реалізації операції Make-Set утворює список із одного елемента, а Find-Set повертає вказівник на початок списку і обидві вимагають часу O(1). Для виконання операції Union (x, y) необхідно додати список, який містить x, до кінця списку, що містить y. При цьому треба також встановити правильні вказівники на початок списку для усіх бувших елементів множини, що містила х; час вказаної операції лінійно залежить від розміру вказаної множини.

PList

next

val

next

val

next

val

Малюнок Х. Однозв’язний список

Малюнок Х. Стек

3

1

2

4

5

6

Малюнок Х. Орієнтований граф. V = {1, 2, ,3, 4, 5, 6},

E = {{1, 3}, {3, 2}, {2, 2}, {2, 4}, {5, 6}}

Граф містить цикл, тому

не є ані деревом, ані лісом

Ліс дерев

Дерево без

виділеного кореня

15