Оператори для роботи із атд “Множина”. Моделі представлення.

MERGE(A, B, C) – об’єднання множин, що неперетинаються. Присвоює С=АÈВ

MEMBER(x, A) – повертає значення true, якщо елемент х належить множині А і значення false, якщо

MAKENULL(A) – присвоює множині А значення порожньої множини.

Insert(X, a) – робить х елементом множини а. Або іншими словами аè{X}.

DELETE(x,A) – видаляє елемент х з множини А. А\{x}.

ASSIGN(A, B) – присвоює множині А в якості значення множину В.

MIN(A) – повертає найменший елемент множини А.

EQUAL (A, B) – повертає значення true, якщо множини А і В складаються з одних і тих самих елементів.

FIND (x) – функція може бути визначена в середовищі, де є деякий набір множин, що не перетинаються. Повертає ім’я множини, в якій міститься елемент х.

Представлення  при допомозі двійкових векторів і при допомозі зв’язаних списків

Реалізація атд “Множина” при допомозі двійкових векторів

Якщо множина, яку ми розглядаємо, є підмножиною деякої великої універсальної множини цілих чисел 1..N, то можна застосувати реалізацію АТД SET при допомозі двійкового  вектора (який називають буловим).В такому випадку, множина є представлена двійковим вектором, в якому і-й біт рівний 1(true), якщо i є елементом множини.Перевагою такої реалізації є те, що оператори MEMBER, INSERT і DELETE можна виконати за фіксований проміжок часу. А якщо універсальна множина настільки мала, що двійковий вектор займає не більше розміру змінної, то оператори UNION, INTERSECTION і DIFFERENCE можна виконати з допомогою простих логічних операцій над двійковими векторами (and, or, andnot).

function UNION (SET A, SET B, SET C)

      for I from 0 to NUM do

            C = A or B;

Для реалізації операторів INTERSECTION чи DIFFERENCE необхідно логічну операцію or замінити на and чи and not відповідно.

Реалізація атд “Множина” при допомозі зв’язаних списків

Множини можна представляти у вигляді зв’язаного списку, коли елементи, що знаходяться в списку вважаються елементами, що містяться в множині.

На відміну від представлення при допомозі двійкових векторів, в даному випадку простір, який займає АТД пропорційний розміру, який займає сама множини, а не розміру її універсальної множини. Крім того таке представлення є більш загальним, оскільки тут множини не повинні бути підмножинами деякої універсальної множини.

function INTERSECTION (celltype↑ ahead, celltype↑ bhead, celltype↑ pc) {

celltype↑ acurrent, bcurrent, ccurrent;

acurrent = ahead->next;

bcurrent = bhead->next;

ccurrent = pc;

while (acurrent ≠ NULL) and (bcurrent ≠ NULL) do

if acurrent->element == bcurrent->element

then

new ccurrent->next

ccurrent = ccurrent->next

ccurrent->element = accurent->element;

acurrent = acurrent->next;

bcurrent = bcurrent->next;

else

if acurrent->element < bcurrent->element

then acurrent = acurrent->next;

else bcurrent = bcurrent->next;

ccurrent->next=NULL; }

Атд “Словник”. Реалізація словників

Словники можна представити при допомозі відсортованих чи не відсортований списків. Інша можлива реалізація словників з використанням двійкових векторів, за умови, що елементи даної множини є цілими числами 1,…,N.Ще один варіант реалізації - з використанням масивів фіксованої довжини  з вказанням на останню заповнену комірку цього масиву. Така реалізація можлива, якщо нам точно відомо, що розмір словника не стане більшим за задану розмірність масиву.

struct DICTIONARY

int last

nametype data[1..maxsize]

function MAKENULL (DICTIONARY A)

A.last = 0;

function MEMBER (nametype x, DICTIONARY A)

for i from 1 to A.last do

if A.data == x

then return true

return false;

function INSERT (nametype x, DICTIONARY A)

if MEMBER (x, A) == false

then

if A.last < maxsize

then

A.last = A.last +1;

A.data[A.last] = x;

Else error (“словник заповнений”);

function DELETE (nametype x, DICTIONARY A)

int i;

if A.last > 0

then

for i=1 to A.last do

if A.data == x

then

A.data = A.data[last]

A.last = A.last - 1