Дек - это двунаправленная очередь, т.е. линейный список, в котором все включения и исключения (и обычно всякий доступ) достигаются на обоих концах списка:
левый
второй
правый
конец
слева
справа
EL1
EL2
..
Eln-1
Eln
включить
или
исключить
Более точно следует представить так:
EL3
*
…
nil
Для организации дека в виде динамической цепочки необходимо иметь следующие типы:
type SS = ^ZVENO;
ZVENO = record
ELEM: integer;
next: SS;
pred: SS;
end.
Очевидно, что дек обладает большей общностью, чем стек и очередь; он имеет некоторые общие свойства с каждой из этих структур. Существуют деки с ограниченным входом (реестры) и выходом (архивы). В таких деках соответственно включение и исключение допускается только в одном конце.
Строго говоря, при работе с деками достаточно иметь ссылку на один любой элемент. Однако для удобства создадим процедуру, при выходе из которой есть ссылки на оба конца дека:
procedure FORMIR_DEK_1(var L, R: SS);
var Z: SS; EL: integer;
begin
¦ new(L); read(L^.elem);
¦ L^.pred:= nil; R:= L; Z:= L;
¦ WHILE R^.elem <> 0 do
¦ begin
¦ ¦ new(R^.next); R:=R^.next;
¦ ¦ read(r^.elem); R^.pred:= Z; Z:= R;
¦ end;
¦ R^.next:= nil; readln;
ПРИМЕЧАНИЕ. В рассмотренном примере для образования дека используются три ссылочные переменные: L - начало дека, R - конец дека, Z - промежуточное звено. Однако эта программа может быть упрощена за счет использования более сложных ссылок типа R^.NEXT^.ELEM и R^.NEXT^.PRED.
Рассмотрим подробно эти объекты. Пусть ссылочная переменная Z указывает на текущее звено дека:
Звено 1
Звено 2
X
next
pred
ELi
ELi+1
При таких обозначениях динамическая переменная Z^.NEXT^.ELEM означает числовое поле звена 2 (т.е элемент ELi+1), а переменная Z^.NEXT^.PRED - поле PRED звена 2. Учитывая эти соображения, представим программу формирования дека следующим образом:
procedure FORMIR_DEK_2(var L, R: SS);
¦ randomize; new(L);
¦ L^.elem:= random (10);
¦ L^.pred:= nil; R:= L;
¦ while R^.elem <> 0 do
¦ begin new(R^.next);
¦ ¦ R^.next^.elem:= random(10);
¦ ¦ R^.next^.pred:= R; R:=R^.next
R^.next:= nil
Для дека справедливы те же операции, что для очереди и стека - вставка и удаление звеньев.
Для процедуры вставки в дек, как и в любой другой линейный список, необходимы два параметра: X - звено, после которого (перед которым) надо поместить элемент, и Y - вставляемое звено. Схема вставки остается такой же, как, например, в очереди, но в деке после включения нового звена нужно установить две связи - на последующий и предыдущий элементы.
Z
Y
EL
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39