yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Быстрая реализация АТД MFSET

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

Быстрая реализация АТД MFSET

Применение алгоритма из листинга 5.13 для последовательного выполнения п - 1 раз оператора MERGE займет время порядка О(п2). Один из способов ускорения выполнения оператора MERGE заключается в связывании всех элементов компонента в отдельные списки компонентов. Тогда при слиянии компонента В в компонент А вместо просмотра всех элементов необходимо будет просмотреть только список элементов компонента В. Такое расположение элементов сократит среднее время слияния компонентов. Но нельзя исключить случая, когда каждое i-e слияние выполняется в виде оператора MERGE(A. В), где компонент А состоит из одного элемента, а В — из і элементов, и результат слияния получает имя компонента А. Выполнение такого оператора требует О(і) шагов, а последовательность п - 1 таких операторов потребует времени порядка  = п(п -1)/2 .

Чтобы избежать описанной ситуации, можно отслеживать размер каждого компонента и всегда сливать меньшее множество в большее. Тогда каждый раз элемент из меньшего множества переходит в множество, которое, по крайней мере, в два раза больше его исходного множества. Поэтому, если первоначально было п компонентов и каждый из них содержал по одному элементу, то любой элемент может перейти в любой компонент не более чем за 1 + logn шагов. Таким образом, в новой версии оператора MERGE время его выполнения пропорционально количеству элементов в компоненте, чье имя изменяется, а общее число таких изменений не больше n(1 + logn), поэтому время всех слияний имеет порядок О(п logn).

Теперь рассмотрим структуру данных, необходимую для такой реализации. Во-первых, необходимо отображение имен множеств в записи, состоящие из

• поля count (счет), содержащего число элементов в множестве, и

• поля firstelement (первый элемент), содержащего индекс ячейки массива с первым элементом этого множества.

Во-вторых, необходим еще один массив записей, индексированный элементами. Здесь записи имеют поля:

setname (имя множества), содержащее имя множества;

nextelement (следующий элемент), значение которого указывает на следующий элемент в списке данного множества.

Будем использовать 0 в качестве маркера конца списка, т.е. значения NIL. В языках программирования, подходящих для таких структур, можно было бы использовать указатели на последний массив, но язык Pascal не разрешает указателей внутрь массивов.

В специальном случае, когда имена множеств и элементы являются целыми числами из интервала от 1 до п, можно использовать массив для реализации отображения, описанного выше. В таком случае возможно следующее объявление:

type

name type = l..n;

elementtype = l..n;

MFSET = record

setheaders:   array[l..n]   of record

{   заголовки списков множеств   }

count:   0..п;

firstelement:   0..n;

end;

names:   array[1..n]   of record

{  массив имен множеств   }

setname:   nametype; nexteleraent:   О…n

end

end;

Процедуры INITIAL, MERGE и FIND представлены в листинге 5.14. На рис. 5.10 показан пример описанной структуры данных, состоящей из множеств 1 = {1, 3, 4}, 2 = {2} и 5 = {5, 6}.

 

79