ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->Листинг 4.3. Процедура INTERSECTION, использующая связанные списки

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

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

procedure INTERSECTION ( ahead, bhead: ↑celltype;

var pc: ↑celltype );

{ Вычисление пересечения сортированных списков А и В с

ячейками заголовков ahead и bhead, результат —

сортированный список, на чей заголовок указывает рс }

var

acurrent, bcurrent, ccurrent: ↑celltype;

{ текущие ячейки списков A и В и последняя ячейка

дополнительного списка С }

begin

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

(2)       acurrent:= aheadf↑ .next;

(3)       bcurrent:= bnead↑.next;

(4)       ccurrent:= pc;

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

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

(6)                      if acurrent↑.element = bcurrent↑. element then begin {  добавление элемента в пересечение  }

(7)                                 nev(ccurrent↑.next);

(8)                                 ccurrent:=  ccurrent↑.next;

(9)                                 ccurrent↑.element:= acurrent↑.element;

(10)                               acurrent:=  acurrent↑.next;

(11)                               bcurrent:= bcurrent↑.next

end

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

(12)                               if acurrent↑.element < bcurrent↑.element then

(13)                               acurrent:=  acurrent↑.next;

else

(14)                                           bcurrent:= bcurrent↑.next

end

(15)                               ccurrent↑.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(A, В) копирует список А в список В. Отметим, что этот оператор нельзя реализовать простым переопределением заголовка списка В на заголовок списка А, поскольку при последующих изменениях в списке В надо будет делать аналогичные изменения в списке А, что, естественно, может привести к нежелательным коллизиям. Оператор MIN реализуется легко — просто возвращается первый элемент списка. Операторы DELETE и FIND можно реализовать, применив общие методы поиска заданного элемента в списках, в случае оператора DELETE найденный элемент (точнее, ячейка, в которой он находится) удаляется.

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

 

47