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

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

Реализация частично упорядоченных деревьев посредством массивов

Исходя из того, что рассматриваемые нами деревья являются двоичными, по возможности сбалансированными и на самом нижнем уровне все листья "сдвинуты" влево, можно применить для этих деревьев необычное представление, которое называется куча. В этом представлении используется массив, назовем его А, в котором первые п позиций соответствуют п узлам дерева. А[1] содержит корень дерева. Левый сын узла A[i], если он существует, находится в ячейке A[2i], а правый сын, если он также существует, — в ячейке A[2i + 1]. Обратное преобразование: если сын находится в ячейке А[і], і > 1, то его родитель — в ячейке A[i div 2]. Отсюда видно, что узлы дерева заполняют ячейки А[1], А[2], ..., А[п] последовательно уровень за уровнем, начиная с корня, а внутри уровня — слева направо. Например, дерево, показанное на рис. 4.6, будет представлено в массиве следующей последовательностью своих узлов: 3, 5, 9, 6, 8, 9, 10, 10, 18, 9.

В данном случае мы можем объявить АТД PRIORITYQUEUE (Очередь с приоритетами) как записи с полем contents для массива элементов типа, например processtype, как в примере 4.9, и полем last целочисленного типа, значение которого указывает на последний используемый элемент массива. Если мы также введем константу maxsize, равную количеству элементов очереди, то получим следующее объявление типов:

type

PRIORITYQUEUE  =  record

contents:   array[1..maxsize]   of  processtype;

last:   integer

end;

Реализация операторов, выполняемых над очередью с приоритетами, показана в следующем листинге.

 

Листинг 4.13. Реализация очереди с приоритетами посредством массива

procedure MAKENULL ( var A: PRIORITYQUEUE );

begin

A.last:= 0

end; { MAKENULL }

procedure INSERT ( x: processtype; var A: PRIORITYQUEUE );

var

і: integer; temp: processtype;

begin

if A.last >= maxsize then

error('Очередь заполнена')

else begin

A.Jast:= A.last + 1;

A.contents[A.last]:= x;

i:= A.last; { і — индекс текущей позиции х }

while (і > 1) and (p(A.contents[і]) <

p(A.contentsdiv 2])) do

begin { перемещение х вверх по дереву путем обмена

местами с родителем, имеющим больший приоритет }

temp:= A.contents[і];

A.contents[і]:= A.contentsfi div 2];

A.contents[і div 2]:= temp;

i:= і div 2

end

end

end; { INSERT }

 

function DELETEMIN ( var A: PRIORITYQUEUE ): ↑processtype;

var

i, j: integer;

temp: processtype;

minimum: ↑processtype;     

begin

if A.last = 0 then

error('Очередь пуста')        

else begin

new (minimum);

minimum ↑ := A.contents[l];

A.contents[1]:= A.contents[A.last];

A.last:= A.last - 1;

i:= 1;

while і <= A.last div 2 do begin

{ перемещение старого последнего элемента

вниз по дереву }

if (p(A.contents[2*i]) < р(A.contents[2*і + 1] ) )

or (2*1 = A.last) then

j:= 2*1

else

j:= 2*1 + 1;

{ j будет сыном і с наименьшим приоритетом или,

если 2*1 = A.last, будет просто сыном і }

if p(A.contents[i]) > р(A.contents[j]) then begin

{ обмен старого последнего элемента с сыном,

имеющим наименьший приоритет }

temp:= A.contents[i];

A.contents[i]:= A.contents[j];

A.contents[j]:= temp;

i:= j;

end

else

return(minimum)

( дальше перемещение элемента невозможно }

end;

return(minimum) { элемент дошел до листа }

end

end; { DELETEMIN }

 

 

62