yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->4.4. Реализация множеств посредством связанных списков

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

4.4. Реализация множеств посредством связанных списков

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

При реализации оператора INTERSECTION (Пересечение) в рамках представления множеств посредством связанных списков есть несколько альтернатив. Если универсальное множество линейно упорядочено, то в этом случае множество можно представить в виде сортированного списка, т.е. предполагая, что все элементы множества сравнимы посредством отношения "<", можно ожидать, что эти элементы в списке будут находиться в порядке е1, е2, ..., еп, когда е1 < е2 < e3 < … < еп. Преимущество отсортированного списка заключается в том, что для нахождения конкретного элемента в списке нет необходимости просматривать весь список.

Элемент будет принадлежать пересечению списков l1 и L2 тогда и только тогда, когда он содержится в обоих списках. В случае несортированных списков мы должны сравнить каждый элемент списка l1 с каждым элементом списка L2, т.е. сделать порядка О(n2) операций при работе со списками длины п. Для сортированных списков операторы пересечения и некоторые другие выполняются сравнительно просто: если надо сравнить элемент е списка L1 с элементами списка L2, то надо просматривать список l2 только до тех пор, пока не встретится элемент е или больший, чем е. В первом случае будет совпадение элементов, второй случай показывает, что элемента е нет в списке L2. Более интересна ситуация, когда мы знаем элемент d, который в списке l1 непосредственно предшествует элементу е. Тогда для поиска элемента, совпадающего с элементом е, в списке L2 можно сначала найти такой элемент f, что d≤f, и начать просмотр списка L2 с этого элемента. Используя этот прием, можно найти совпадающие элементы в списках l1 и L2 за один проход этих списков, продвигаясь вперед по спискам в прямом порядке, начиная с наименьшего элемента. Код процедуры, реализующей оператор INTERSECTION, показан в листинге 4.3. Здесь множества представлены связанными списками ячеек, чей тип определяется следующим образом:

type

се11type = record

element:   elementtype;

next:   ↑celltype

end

В листинге 4.3 предполагается, что elementtype — это тип целых чисел, которые можно упорядочить посредством обычного оператора сравнения <. Если elementtype представлен другим типом данных, то надо написать функцию, которая будет определять, какой из двух заданных элементов предшествует другому элементу.

 

 

46