Алгоритмический язык Паскаль
K:SS;
New(K);
K^.elem:=el;
![]()
![]()
![]()
New(K);
![]()
EL:=random(10);
![]()
![]()
![]()
![]()
![]()
ST:=K;
![]()
![]()
![]()
![]()
Запишем теперь саму процедуру формирования стека:
procedure SOZDAN_STACK (var ST: SS);
var K: SS;
EL: integer;
begin
randomize;
EL:= random(10);
new(ST); ST:= nil;
while EL <> 0 do
begin
¦ new(K); K^.elem:= EL;
¦ k^.next:= ST; ST:= K;
¦ EL:= random(10);
end;
end.
ЗАМЕЧАНИЕ. Как видно из процедуры, организация очереди и стека отличается только порядком установления связи: предыдущий элемент очереди указывает на следующий, а следующий элемент стека ссылается на предыдущий.
Известно, что новый элемент всегда вставляется на первое место - в вершину стека. Отсюда получаем схему вставки звена в стек:
|
|
* | Eln | * | … | EL1 | nil | ||||
|
|
Eln+1 | * |
Процедура имеет два параметра: ST - указатель на стек, EL - заносимый элемент:
PROCEDURE VSTAVKA_V_STACK(var ST: SS; EL: integer);
var K: SS;
begin
new(K); K^.elem:= EL;
K^.next:= ST; ST:= K
end.
Схематически процесс удаления можно изобразить так:
|
|
* | Eln | * | Eln-1 | * | … | EL1 | nil | ||
|
|
По схеме видно, что удаляется N-е звено (вершина стека), которое надо запомнить в специальной ячейке SKLAD:
procedure UDALENIE_IZ_STACK(var ST: SS; var SKLAD: integer);
begin
¦ SKLAD:= ST^.elem;
¦ ST:= ST^.next
end.
Мы видим, что здесь переменная ST начинает хранить ссылку на N-1 элемент.
Данная процедура имеет недостатки:
1) предполагается, что стек заведомо не пуст, иначе программа зависнет;
2)
исключаемое
звено не уничтожается,
т.к. меняется
только ссылка
в переменной
ST. Если таких
удалений несколько,
то память будет
забита "мусором".
Поэтому следует
исключить
элементы не
только из списка,
но и из памяти.
Для этого можно
использовать
процедуру
DISPOSE.
Указанные недостатки учтены в следующей процедуре:
procedure UDALENIE_MOD(var ST: SS; var SKLAD: integer);
var K: SS;
begin
¦ if ST = nil then writeln('стек пустой')
¦ else begin
¦ ¦ SKLAD:= ST^.elem; K:=ST;
¦ ¦ ST:= ST^.next; dispose(K);
end;
end.
Здесь мы ввели в употребление вспомогательную ссылочную переменную К, т.к. писать DISPOSE (ST) нельзя, ведь ST содержит ссылку на вершину стека.
Для извлечения из стека N-го элемента необходимо поступить так же, как при выборке элемента из файла, - "прокрутить" стек на N-1 позиций и затем извлечь N-й элемент. Для "прокрутки" стека можно воспользоваться процедурой UDALENIE, т.к. удаление в динамических структурах означает не уничтожение звеньев списка, а только передвижение указателя на следующий элемент.
Для написания этой процедуры следует уточнить, что под N-м элементом стека следует понимать элемент, отстоящий на N позиций от вершины стека:
procedure VIBORKA_IZ_STACKA(var ST: SS; var SKLAD: integer;
N: integer);
var K: SS; i: integer;
begin
¦ K:= ST;
¦ for i:= 1 to N-1 do
¦ UDALENIE_IZ_STACK(K, SKLAD);
¦ SKLAD:= K^.elem;
end.
Для вывода на печать элементов стека можно воспользоваться процедурой печати для цепочки, т.к. в этом смысле цепочка ничем не отличается от стека. Отметим только, что элементы стека будут выведены в порядке, обратном его заполнению.
14.3 Дек
Дек - это двунаправленная очередь, т.е. линейный список, в котором все включения и исключения (и обычно всякий доступ) достигаются на обоих концах списка:
| левый | второй | второй | правый | ||||||
| конец | слева | справа | конец | ||||||
|
|
EL1 | EL2 | .. | .. | Eln-1 | Eln | |||
|
|
|||||||||
| включить | включить | ||||||||
| или | или | ||||||||
| исключить | исключить | ||||||||
Более точно следует представить так:
| EL1 | EL2 | EL3 | Eln | |||||||||
|
|
* | * | * | … | * | 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;
end.
ПРИМЕЧАНИЕ. В рассмотренном примере для образования дека используются три ссылочные переменные: L - начало дека, R – конец дека, Z - промежуточное звено. Однако эта программа может быть упрощена за счет использования более сложных ссылок типа R^.NEXT^.ELEM и R^.NEXT^.PRED.
Рассмотрим подробно эти объекты. Пусть ссылочная переменная Z указывает на текущее звено дека:
| Звено 1 | Звено 2 | ||||||
|
|
* | next | next | … | |||
|
|
… | pred | pred | ||||
| ELi | ELi+1 | ||||||
При таких обозначениях динамическая переменная Z^.NEXT^.ELEM означает числовое поле звена 2 (т.е элемент ELi+1), а переменная Z^.NEXT^.PRED - поле PRED звена 2. Учитывая эти соображения, представим программу формирования дека следующим образом:
procedure FORMIR_DEK_2(var L, R: SS);
begin
¦ 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
¦ end;
R^.next:= nil
end.
Для дека справедливы те же операции, что для очереди и стека - вставка и удаление звеньев.
Для процедуры вставки в дек, как и в любой другой линейный список, необходимы два параметра: X - звено, после которого (перед которым) надо поместить элемент, и Y - вставляемое звено. Схема вставки остается такой же, как, например, в очереди, но в деке после включения нового звена нужно установить две связи – на последующий и предыдущий элементы.
|
|
ELi | Z | * | ELi+1 | ||||||
|
|
* | * | * | |||||||
|
|
… | * | Y | * | * | … | ||||
|
|
||||||||||
| EL | ||||||||||
|
|
* | |||||||||
|
|
* | |||||||||
Рассмотрим предварительно схему связи между звеньями дека в процессе вставки нового элемента:
| ОПЕРАТОРЫ | ПОЯСНЕНИЕ | ||||||
| Z | |||||||
| X | Elx | Elz | |||||
|
|
* | * | |||||
|
|
* | Y | Ely | * | |||
|
|
* | ||||||
| * | |||||||
| Z | |||||||
| X | Elx | Elz | |||||
|
|
* | * | |||||
|
|
* | Y | Ely | * | |||
|
|
* | ||||||
|
|
* | ||||||
| Z | |||||||
| X | Elx | Elz | |||||
|
|
* | * | |||||
|
|
* | Y | Ely | * | |||
|
|
* | ||||||
|
|
* | ||||||
| Z | |||||||
| X | Elx | Elz | |||||
|
|
* | * | |||||
|
|
* | Y | Ely | * | |||
|
|
* | ||||||
|
|
* | ||||||
Процедура вставки нового звена 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);
var X: SS;
begin
¦ N:= 1; X:= Y;
¦ while (X^.elem <> ZNACH) and (X^.next <> nil) do
¦ begin
¦ ¦ X:= X^.next; Z:= X;
¦ ¦ N:= N+1
¦ end;
¦ if X^.next = nil then
¦ begin N:= 0; Z:= nil; end;
end.
ПОЯСНЕНИЕ. С помощью данной процедуры в списке Y ищется звено с элементом ZNACH. Значение переменной N дает номер искомого звена, а переменная Z - ссылку на это звено. Если такого звена нет, то N = 0 и Z = NIL.
Сортировка линейных списков незначительно отличается от сортировки массивов. При этом надо помнить, что при сортировке односвязных списков применяются методы, в которых движение идет в одну сторону (здесь пузырьковая сортировка неприемлема). Для двухсвязных списков (деков) таких ограничений нет. Очевидно, что при сортировке динамических объектов происходит не сама их перестановка, а переброска соответствующих ссылок:
procedure SORTSPISOK (var X: SS);
{ X - Ссылка на начало списка }
var X1, Y1:SS; P: integer;
begin
¦ X1:= X; { Выбор элемента для сравнения }
¦ while X1^.next <> nil do { Проход по списку до
¦ предпоследнего элемента}
¦ begin
¦ ¦ Y1:=X1^.next;
¦ ¦ while Y1^.next <> nil do { Проход до последнего
¦ ¦ элемента }
¦ ¦ begin
¦ ¦ ¦ { Перестановка местами элементов}
¦ ¦ ¦ if Y1^.elem < X1^.elem