Рассмотрим предварительно схему связи между звеньями дека в процессе вставки нового элемента:
ОПЕРАТОРЫ
ПОЯСНЕНИЕ
Z
X
Elx
Elz
*
Y^.next:=X^.next;
Y
Ely
Y^.pred:=X;
X^.next:=Y;
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);
¦ Y^.next:= X^.pred^.next; X^.pred^.next:= Y;
¦ Y^.pred:= X^.pred; X^.pred:= Y;
ЗАМЕЧАНИЕ 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);
¦ 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;
В этой процедуре введены параметры-переменные: Y - начало дека и Z - ссылка на конец дека. Они необходимы, т.к. здесь могут быть изменены начало и конец дека.
Если Y^.NEXT = NIL, то это означает, что дек пуст и никаких действий не производится. Равенство X = Y показывает, что дек состоит из одного звена, которое удаляется путем присваивания ссылке Y (началу дека) значения указателя на последнее нулевое звено дека. Для остальных случаев все действия производятся, как и в предыдущем примере.
Как уже говорилось ранее, все виды линейных списков имеют много общего, а именно, они являются динамическими цепочками. Поэтому имеет смысл остановиться на операциях, общих для всех видов линейных списков: вывод, поиск, сортировка. Заметим, что операции вывода и поиска уже рассматривались для некоторых частных случаев линейных списков. Здесь же будут даны универсальные процедуры.
Процедура печати списка имеет вид:
procedure VIVOD_SPISOK(var Y: SS);
var X: SS;
begin X:= Y;
¦ while X^.next <> nil do
¦ begin
¦ ¦ write(X^.elem,' '); X:=X^.next;
ПОЯСНЕНИЕ. Здесь Y - начало списка, а переменная X введена, чтобы после печати списка значение переменной Y не изменилось (не потерялось начало списка).
Поиск заданного элемента в списке осуществляется чаще всего не для констатации факта присутствия этого элемента, а для его удаления или для вставки после него (перед ним в деке) нового элемента. Именно поэтому возвращаемым параметром этой процедуры должна быть ссылка на данный элемент (если такой факт имеет место). Кроме того, полезно знать и номер найденного звена от начала списка:
procedure POISK_V_SPISKE(var Y,Z: SS; ZNACH: integer;
var N: integer);
¦ N:= 1; X:= Y;
¦ while (X^.elem <> ZNACH) and (X^.next <> nil) do
Страницы: 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
