будут находиться в порядке е, е, е„, когда ei < ег < вз < ... < с„. Преимущество отсортированного списка заключается в том, что для нахождения конкретного элемента в списке нет необходимости просматривать весь список.

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

type

celltype = record

eienient: elementtype; next: tcelltype

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

Листинг 4.3. Процедура INTERSECTION, использующая связанные списки

procedure INTERSECTION ( ahead, bhead: Tcelltype; var pc: Tcelltype ) ,-{ Вычисление пересечения сортированных списков А и В с ячейками заголовков ahead и bhead, результат - сортированный список, на чей заголовок указывает рс }

acurrent, bcurrent, ccurrent: Tcelltype; { текущие ячейки списков и В и последняя ячейка дополнительного списка С }

begin

(1) new(pc); { создание заголовка для списка С }

(2) acurrent: = aheadt. next;

(3) bcurrent:= bheadt.next;

(4) ccurrent:= pc;

(5) while (acurrent <> nil) and (bcurrent <> nil) do begin

{ сравнение текущих элементов списков А и В }

(6) if аcurrentt. element = bcurrentt. element then begin

{ добавление элемента в пересечение }

(7) new(ccurrentT.next) ;

(8) ccurrent:= ccurrentt.next;

(9) ccurrentT.elenient:= acurrent?. element;

(10) acurrent: = acurrentt. next;

(11) bcurrent:= bcurrentt. next end

else { элементы неравны }

(12) if acurrentt. element < bcurrentT. element then

(13) acurrent:= acurrentT. next; else

(14) bcurrent:= bcurrentt. next end

(15) ccurrentT. next: = nil

end; { INTERSECTION }

Связанные списки в листинге 4.3 в качестве заголовков имеют пустые ячейки, которые служат как указатели входа списков. Читатель при желании может написать эту программу в более общей абстрактной форме с использованием примитивов списков. Но программа листинга 4.3 может быть более эффективной, чем абстрактная программа. Например, в листинге 4.3 используются указатели на отдельные ячейки вместо "позиционных" переменных, указывающих на предыдущую ячейку. Так можно сделать вследствие того, что элементы добавляются в список С, а списки А и В только просматриваются без вставки или удаления в них элементов.

Процедуру INTERSECTION листинга 4.3 можно легко приспособить для реализации операторов UNION и DIFFERENCE. Для выполнения оператора UNION надо все элементы из списков А и В записать в список С. Поэтому, когда элементы не равны (строки 12-14 в листинге 4.3), наименьший из них заносится в список С, так же, как и в случае их равенства. Элементы заносятся в список С до тех пор, пока на исчерпаются оба списка, т.е. пока логическое выражение в строке 5 не примет значение false. В процедуре DIFFERENCE в случае равенства элементов они не заносятся в список С. Если текущий элемент списка А меньще текущего элемента списка В, то он (текущий элемент списка А) заносится в список С. Элементы заносятся в список С до тех пор, пока не исчерпается список (логическое условие в строке 5).

Оператор ASSIGN (А, В) копирует список А в список В. Отметим, что этот оператор нельзя реализовать простым переопределением заголовка списка В на заголовок списка А, поскольку при последующих изменениях в списке В надо будет делать аналогичные изменения в списке А, что, естественно, может привести к нежелательным коллизиям. Оператор MIN реализуется легко - просто возвращается первый элемент списка. Операторы DELETE и FIND можно реализовать, применив общие методы поиска заданного элемента в списках, в случае оператора DELETE найденный элемент (точнее, ячейка, в которой он находится) удаляется.

Реализовать оператор вставки нового элемента в список таюке неслокно, но он должен стоять не в произвольной позиции в списке, а в "правильной" позиции, учитывающей взаимный порядок элементов. В листинге 4.4 представлен код процедуры INSERT (Вставка), которая в качестве параметров имеет вставляемый элемент и указатель на ячейку заголовка списка, куда вставляется элемент. На рис. 4.2 показаны ключевые ячейки и указатели до и после вставки элемента (старые указатели обозначены сплошными линиями, а новые - пунктирными).

Листинг 4.4. Процедура вставки элемента

procedure INSERT ( х: elementtype; р: tcelltype ) ; var

current, newcell: Tcelltype; begin

current:= p;

while currentT.next <> nil do begin

if currentt. nextt. element = x then

return; { элемент x уже есть в списке } if currentT.nextt. element > x then

add:

end;

goto add; { далее останов процедуры } current:= current?, next

end;

{здесь current - ячейка, после которой надо вставить х} new{newcell) ; newcellT. element:= х; newcellT. next: = current?.next; current?.next:= newcell

{ INSERT }

1----------:--£

current

Puc. 4.2. Схема вставки нового элемента

4.5. Словари

Применение множеств при разработке алгоритмов не всегда требует таких мощных операторов, как операторы обьединения и пересечения. Часто достаточно только хранить в множестве "текущие" обьекты с периодической вставкой или удалением некоторых из них. Время от времени также возникает необходимость узнать, присутствует ли конкретный элемент в данном множестве. Абстрактный тип множеств с операторами INSERT, DEEETE и MEMBER называется DICTIONARY (Словарь). Мы также включим оператор MAKENULL в набор операторов словаря - он потребуется при реализации АТД для инициализации структур данных. Далее в этом разделе мы приведем пример использования словарей, а в следующем разделе рассмотрим реализации, подходящие для представления словарей.

Пример 4.2. Общество защиты тунцов (ОЗТ) имеет базу данных с записями результатов самого последнего голосования законодателей по законопроектам об охране тунцов. База данных состоит из двух списков (множеств) имен законодателей, которые названы goodguys (хорощие парни) и badguys (плохие парни). ОЗТ прощает законодателям их прощдые "ощибки", но имеет тенденцию забывать своих "друзей", которые ранее голосовали "правильно". Например, после голосования по законопроекту об ограничении вылова тунца в озере Эри все законодатели, проголосовавщие за этот законопроект, заносятся в список goodguys и удаляются из списка badguys, тогда как над оппонентами этого законопроекта совершается обратная процедура. За-

4.5. СЛОВАРИ