1. Реализация атд «множество» посредством двоичных векторов
Наилучшая
конкретная реализация абстрактного
типа данных
(Множество) выбирается исходя из набора
выполняемых операторов и размера
множества. Если все рассматриваемые
множества будут подмножествами небольшого
универсального множества целых чисел
для некоторого фиксированного
,
тогда можно применить реализацию
посредством двоичного (булева) вектора.
В
этой реализации множество представляется
двоичным вектором, в котором
-й
бит равен единице или
,
если
является элементом множества. Главное
преимущество
этой реализации состоит в том, что здесь
операторы
,
и
можно выполнить за фиксированное время
(независимо от размера множества) путем
прямой адресации к соответствующему
биту. Но операторы
,
и
выполняются за время, пропорциональное
размеру универсального множества.
Если
универсальное множество так мало, что
двоичный вектор занимает не более одного
машинного слова, то операторы
,
и
можно выполнить с помощью простых
логических операций (конъюнкции и
дизъюнкции), выполняемых над двоичными
векторами.
Недостатком этой реализации является требование ограниченности универсального множества, а также то, что затраты памяти на хранение каждого множества равны мощности универсального множества.
2. Реализация атд «множество» с помощью массивов
Главным достоинством массива по сравнению с бинарным вектором является отсутствие ограничения на тип элементов, хранимых массивом. Это свойство позволяет хранить в массиве как простые типы данных, строки и вещественные числа, так и структуры данных, которые представляют более сложную реализацию. Так же стоит отметить скорость доступа к -му элементу, где - индекс элемента в массиве.
Из недостатков стоит отметить низкую скорость поиска элемента, так как приходится, в худшем случае, перебирать все элементы множества. Так же, как для бинарных векторов, ограничено количество элементов, которое задается при инициализации массива. Возможны операции изменения размерности массива, но они несут определенную затрату ресурсов и могут существенно снизить производительность системы.
3. Реализация атд «множество» посредством связанных списков
Рассмотрим представление множеств посредством связанных списков, когда элементы списка являются элементами множества. Преимущество данной реализации по сравнению с представлением множеств двоичными векторами, в том, что занимаемое множеством пространство пропорционально размеру представляемого множества, а не размеру универсального множества. Кроме того, представление посредством связанных списков является более общим, поскольку здесь множества не обязаны быть подмножествами некоторого конечного универсального множества.
Представление множества связанным списком ячеек определяется следующим образом:
type TElementType = integer;
type
pDlist = ^TDList;
TDList = record
element:TElementType;
next:pDList;
end;
Данная структура хранит в себе значение элемента и ссылку на следующий элемент. Поле element имеет тип TElementType, этот тип должен быть определен раньше, чем структура TDList, и содержать тип элементов множества. Это могут быть как целые или дробные числа, так и строки или любой другой тип. Поле next имеет тип ссылка на элемент типа TDList. Оно используется для доступа к следующему элементу списка.
Большинство операторов множеств, реализованных как списки, требуют O(N) времени, где N – количество элементов во множестве. Это объясняется необходимостью просматривать в худшем случае последовательно все элементы списка в порядке их следования.
Исключение, например, составляет оператор INSERT для неупорядоченных списков. Его сложность O(1), так как выполняется вставка элемента в начало списка, что не требует просмотра всех его элементов.