Алгоритмический язык Паскаль (стр. 24 из 31)

¦ while R^.elem <> 0 do

¦ begin new(R^.next);

¦ ¦ R^.next^.elem:= random(10);

¦ ¦ R^.next^.pred:= R; R:=R^.next

¦ end;

R^.next:= nil

end.

Для дека справедливы те же операции, что для очереди и стека - вставка и удаление звеньев.

Для процедуры вставки в дек, как и в любой другой линейный список, необходимы два параметра: X - звено, после которого (перед которым) надо поместить элемент, и Y - вставляемое звено. Схема вставки остается такой же, как, например, в очереди, но в деке после включения нового звена нужно установить две связи – на последующий и предыдущий элементы.

	ELi	Z	*	ELi+1
X	*	*	*
	…	*	Y	*	*	…
EL
	*
	*

Рассмотрим предварительно схему связи между звеньями дека в процессе вставки нового элемента:

ОПЕРАТОРЫ	ПОЯСНЕНИЕ
Z
X	Elx	Elz
	*	*
Y^.next:=X^.next;	*	Y	Ely	*
	*
*
Z
X	Elx	Elz
	*	*
Y^.pred:=X;	*	Y	Ely	*
	*
	*
Z
X	Elx	Elz
X^.next:=Y;	*	*
	*	Y	Ely	*
	*
	*
Z
X	Elx	Elz
	*	*
	*	Y	Ely	*
Y^.next^.pred:=Y;	*
	*

Процедура вставки нового звена Y в дек после звена X принимает вид:

procedure VSTAVKA_V_DEK_POSLE(X, Y: SS);

begin

¦ Y^.next:= X^.next;

¦ Y^.pred:= X;

¦ X^.next:= Y;

¦ Y^.next^.pred:= Y;

end.

ЗАМЕЧАНИЕ 1. Мы рассмотрели теперь процедуры вставки нового звена во все виды линейных списков с односторонней связью (цепочки, очереди, стеки) и в дек. Однако во всех этих процедурах новое звено вставлялось ПОСЛЕ указанного звена (в стеке - в вершину, в очереди - в хвост). Конечно, можно в односвязном линейном списке поставить новый элемент и ПЕРЕД указанным, но это требует некоторых дополнительных операций. Например, можно новый элемент поместить в следующее звено, а затем произвести обмен информационными полями. В деке же возможна прямая вставка звена ПЕРЕД указанным с использованием ссылки PRED. В результате получаем:

procedure VSTAVKA_V_DEK_PERED(X, Y: SS);

begin

¦ Y^.next:= X^.pred^.next; X^.pred^.next:= Y;

¦ Y^.pred:= X^.pred; X^.pred:= Y;

end.

ЗАМЕЧАНИЕ 2. При вставке нового звена Y в дек относительно X следует учитывать, что на момент применения рассмотренных процедур звенья X и Y уже сформированы и значения этих ссылочных переменных определены. Так, например, звено Y можно сформировать следующим образом:

NEW(Y); Y^.NEXT:= NIL; Y^.PRED:= NIL; READ(Y^.ELEM).

Что касается звена X, то здесь возможны два случая:

1) известен адрес (ссылка) на элемент X; тогда при обращении к процедуре уже задано значение фактического параметра;

2) известен только сам элемент (информационное поле звена X);

для определения ссылки на звено X в указанном деке следует "прокрутить" дек до этого звена (подобно поиску N-го звена в стеке).

Заметим также, что обе процедуры неприменимы для дека, состоящего из одного звена.

При удалении звена из дека, как и в любом линейном списке, происходит перебрасывание ссылок через удаляемое звено: ссылка NEXT предыдущего звена получает своим значением адрес третьего звена, а ссылка PRED третьего звена указывает на первое звено. В результате второе (удалямое) звено X оказывается изолированным от остальных звеньев, что и означает его удаление из дека.

ЗАМЕЧАНИЕ. Данная процедура применима только для звена X, находящегося внутри дека. Для пограничных случаев, когда звено X является первым или единственным, необходимо использовать более сложную процедуру:

procedure UDAL_DEK_1(X: SS; VAR Y, Z: SS);

begin

¦ if Y^.next = nil then writeln('Декпуст !') else

¦ if X = Y then Y:= Y^.next else

¦ begin x^.pred^.next:=x^.next;

¦ ¦ {Переброскассылки next вверху}

¦ ¦ x^.next^.pred:=x^.pred;

¦ ¦ {Переброска ссылки pred внизу}

¦ end;

end.

В этой процедуре введены параметры-переменные: Y - начало дека и Z - ссылка на конец дека. Они необходимы, т.к. здесь могут быть изменены начало и конец дека.

Если Y^.NEXT = NIL, то это означает, что дек пуст и никаких действий не производится. Равенство X = Y показывает, что дек состоит из одного звена, которое удаляется путем присваивания ссылке Y (началу дека) значения указателя на последнее нулевое звено дека. Для остальных случаев все действия производятся, как и в предыдущем примере.

14.4 Общие приемы работы с линейными списками

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

Процедура печати списка имеет вид:

procedure VIVOD_SPISOK(var Y: SS);

var X: SS;

begin X:= Y;

¦ while X^.next <> nil do

¦ begin

¦ ¦ write(X^.elem,' '); X:=X^.next;

¦ end;

end.

ПОЯСНЕНИЕ. Здесь Y - начало списка, а переменная X введена, чтобы после печати списка значение переменной Y не изменилось (не потерялось начало списка).

Поиск заданного элемента в списке осуществляется чаще всего не для констатации факта присутствия этого элемента, а для его удаления или для вставки после него (перед ним в деке) нового элемента. Именно поэтому возвращаемым параметром этой процедуры должна быть ссылка на данный элемент (если такой факт имеет место). Кроме того, полезно знать и номер найденного звена от начала списка:

procedure POISK_V_SPISKE(var Y,Z: SS; ZNACH: integer;

var N: integer);