ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->Простая реализация АТД MFSET

Алгоритмы структуры данных

Простая реализация АТД MFSET

Начнем с простейшего АТД, реализующего операторы MERGE и FIND. Этот АТД, назовем его MFSET (Множество с операторами MERGE и FIND), можно определить как множество, состоящее из подмножеств-компонентов, со следующими операторами.

1. MERGEOA, В) объединяет компоненты А и В, результат присваивается или А, или В.

2. FIND(x) — функция, возвращающая имя компонента, которому принадлежит х.

3. INITIALCA, х) создает компонент с именем А, содержащим только элемент х.

Для корректной реализации АТД MFSET надо разделить исходные типы данных или объявить, что MFSET состоит из данных двух разных типов — типа имен множеств и типа элементов этих множеств. Во многих приложениях можно использовать целые числа для имен множеств. Если общее количество элементов всех компонент равно п, то можно использовать целые числа из интервала от 1 до п для идентификации элементов множеств. Если принять это предположение, то в таком случае существенно, что номерами элементов можно индексировать ячейки массива. Тип имен компонентов не так важен, поскольку это тип ячеек массива, а не индексов. Но если мы хотим, чтобы тип элементов множеств был отличным от числового, то необходимо применить отображение, например посредством хеш-функции, ставящее в соответствие элементам множеств уникальные целые числа из заданного интервала. В последнем случае надо знать только общее число элементов всех компонентов.

После всего сказанного не должно вызывать возражений следующее объявление типов:

const

n =   {  количество всех элементов   };

type

MFSET  =  array[l..n]   of  integer;

или объявление более общего типа

array[интервал элементов]   of   (тип имен множеств)

Предположим, что мы объявили тип MFSET как массив components (компоненты), предполагая, что components[x] содержит имя множества, которому принадлежит элемент х. При этих предположениях операторы АТД MFSET реализуются легко, что видно из листинга 5.13 с кодом процедуры MERGE. Процедура INITIAL(A, x) просто присваивает components[x] значение А, а функция FIND(x) возвращает значение components[x].

Листинг 5.13. Процедура MERGE

procedure MERGE   (   А,   В:   integer;   var  С:   MFSET   );

var

x:   1. . n ;

begin

for x:=  1  to n do

if  C[x]   =  В then

C[x]:=  A

end,   {  MERGE   }

Время выполнения операторов при такой реализации MFSET легко проанализировать. Время выполнения процедуры MERGE имеет порядок О(п), а для INITIAL и FIND время выполнения фиксировано, т.е. не зависит от п.

 

78