КОЛЬЦА (двунаправленный списк)

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

Type ukazat= ^S;
S= record
Inf: integer;
Next: ukazat;
Pred: ukazat;
End;

Динамическая структура, состоящая из звеньев такого типа, называется двунаправленным списком, который схематично можно изобразить так:

Наличие в каждом звене двунаправленного списка ссылки как на следующее, так и на предыдущее звено позволяет от каждого звена двигаться по списку в любом направлении. По аналогии с однонаправленным списком здесь есть заглавное звено. В поле Pred этого звена фигурирует пустая ссылка nil, свидетельствующая, что у заглавного звена нет предыдущего (так же, как у последнего нет следующего).

В программировании двунаправленные списки часто обобщают следующим образом: в качестве значения поля Next последнего звена принимают ссылку на заглавное звено, а в качестве значения поля Pred заглавного звена – ссылку на последнее звено:

Как видно, здесь список замыкается в своеобразное «кольцо»: двигаясь по ссылкам, можно от последнего звена переходить к заглавному звену, а при движении в обратном направлении – от заглавного звена переходить к последнему. Списки подобного рода называют кольцевыми списками.

Существуют различные методы использования динамических списков:

СТЕК

особый вид списка, обращение к которому идет только через указатель на первый элемент. Если в стек нужно добавить элемент, то он добавляется впереди первого элемента, при этом указатель на начало стека переключается на новый элемент. Алгоритм работы со стеком характеризуется правилом: «последним пришел – первым вышел».

Начнем с рассмотрения примера. Пусть в трубку с запаянным концом закатываются шарики. Извлекать их можно только в обратном порядке: тот шарик, что закатился последним, будет извлечен первым.

Подобным образом можно организовать и данные. Стек – такая структура динамических данных, которая состоит из переменного числа компонент одинакового типа. Компоненты извлекаются из стека таким образом, что первой выбирается та компонента, которая была помещена последней. Извлеченная компонента в стеке не сохраняется.

Пример. Рассмотрим последовательные этапы засылки с стек чисел 1, 2, 3.

На этапе б) обращение к процедуре извлечения из стека дает число 2, на этапе в) – число 3.

Опишем стек, в который можно помещать цепочку динамических переменных:

Type

stackp = ^stackcomp;

stackcomp = record

I: integer;

P: stackp

end;

Var

S: stackp;

Если помещать в этот стек последовательность 1, 2, 3, то получится следующий вид:

Поместить в такой стек компоненту можно, например, процедурой SN:

S:= nil;

…

procedure SN(k: integer);

Var

inew: stackp;

Begin

{резервируется память под новую компоненту,

в inew засылается адрес этой компоненты}

new(inew);

with inew do begin

I:= k;

P:= S

end;

S:= inew;

end;

Если со стеком вида как на рисунке выше обратиться к процедуре SN для засылки числа 4, то получим стек вида:

Процедура извлечения компоненты из такого стека может иметь следующий вид:

procedure OUT(var k: integer);

Var

iold: stackp;

Begin

iold:= S;

{значение последней компоненты}

k:= iold^.I;

{извлекается и засылается в S значение

соответствующего указателя на 3}

S:= iold^.P;

dispose(iold);

end;

После обращения к процедуре OUT стек вернется к первоначальному виду (1, 2, 3).

Пустым стеком называется стек, не содержащий компонент. Такой стек можно получить, присвоив значение Nil соответствующей ссылочной переменной (в нашем случае S:= nil;).

Если к пустому стеку применить несколько раз процедуру SN, а затем столько же раз процедуру OUT, то получим снова пустой стек.

Замечание. Нельзя применять процедуру OUT к пустому стеку.

Стеки позволяют гибко и экономно использовать память, т.к. в каждый момент в стеке могут находиться только те переменные, которые нужны для дальнейшей работы программы. (В то время как под массивы, например, мы зачастую вынуждены резервировать и держать избыточную память.)

39 ОЧЕРЕДЬ –

это вид списка, имеющего два указателя на первый и последний элемент цепочки. Новые элементы записываются вслед за последним, а выборка элементов идет с первого. Этот алгоритм типа «первым пришел – первым вышел».

Возможно организовать списки с произвольным доступом к элементам. В этом случае необходим дополнительный указатель на текущий элемент.