Зберігання множин і масивів

Множини це структури найпростішого вигляду. В пам‘яті їх можна зображувати двома способами:

1) для кожного елемента множини зберігати в пам‘яті його описання аналогічно до математичного способу задання множини переліком її елементів;

2) визначити всі потенційно можливі елементи множини, а потім для всякої підмножини такої універсальної множини вказувати для кожного можливого елемента, чи належить він даній підмножині, чи ні. Цей спосіб аналогічний предикатній формі задання множини в математиці.

У першому випадку множину зручно зберігати у вигляді вектора або лінійного списку. У другому - використовуються вектори бітів. Для цього пронумеруємо всі можливі елементи множини, наприклад, від 1 до N. Відведемо вектор пам‘яті із М бітів і визначимо множину, встановлюючи в і -й біт одиницю, якщо і -й можливий елемент присутній у даній множині, і нуль - у протилежному випадку. Очевидно, якщо N велике, а конкретна підмножина мала, то краще користуватися першим способом. Другий спосіб має переваги, які дозволяють виконувати операції над множинами за допомогою логічних операцій машинного рівня.

Слід відзначити, що як тільки множина виявиться записаною в пам‘яті, спосіб її зображення визначає на ній індексацію, і різні методи зображення дозволяють по-різному її обробляти. Зображення в пам‘яті масивів очевидне. Найпростіший масив одномірний, який ототожнюється з вектором. Багатомірні масиви також зображуються векторами. Формули для локалізації елементів багатомірного масиву у векторному зображенні наведено в підрозд.6.1. Однак так звані розріджені матриці зображуються в пам‘яті нелінійними ба-гатозв‘язними структурами.