INTERFACE

Стек.

End

End

Then

Вставка заданного элемента в отсортированный 2-связный список.

End

End

Then

Begin

Удаление в 2-связном списке.

Создание 2-связного списка.

Type u = ^Uzl;

Uzl = Record

i :Integer;

L, R :u;

End;

Varh :u;

Procedure Create2List ( Var h :u; n :Word ); {n – количество узлов}

Var t :u; k :Word;

Begin New(h); h^.i := Random(50); h^.L := Nil; t := h; {создали новый узел}

For k:=1 To n-1 Do Begin

New ( t^.R ); и подключили его к R – ccылке предыдущего узла}

t^.R^.L := t; {в ссылочное поле нового узла записали L - ссылку }

t := t^.R; {указатель t переместили на новый узел }

t^.i := Random(50); { заполнили информационное поле нового узла }

End;

t^.R := Nil; { R - ссылка последнего узла равна Nil}

End;

ProcedureDel2List ( Var h :u; a :Integer );

Vart :u;

t := h;

While t <> Nil Do

Ift^.i = a

Ift = h Then Begint := t^.R; Dispose ( t^ .L ); {удаление спереди}

t^.L := Nil; h:=t; Exit;

Else Begint^.L^.R := t^.R; {удаление в середине}

t^.R^.L := t^.L;

Dispose( t ); Exit;

Elset := t^.R; { продвижение вдоль списка}

Writeln( ' нет такого элемента в списке ' );

End;

Procedure Ins2List ( Var h :u; a :Integer );

Vart, s :u;

Begin t := h; New (s ); s^.i := a;

Whilet <> Nil Do Цикл поиска и вставки узла в надлежащее место списка}

If a <= t^.i

Ift = h { если место вставки найдено }

Then Begins^.L := Nil; s^.R := h; { вставка в начало списка }

t^.L := s; h := s; Exit;

Else Begin s^.L := t^.L; t^.L := s; { вставка в середину списка }

s^.R := t; s^.L^.R := s; Exit;

Else If t^.R = Nil {если t указывает на последний элемент,

Then Break { то выход,

Else t := t^.R; иначе продвигаемся вперед}

{ конец цикла While }

If h = Nil

Then Begin h := s; s^.L := Nil; s^.R := Nil; End{ вставка в пустой список }

Else Begin s^.L := t; s^.R := Nil; t^.R := s; End; { вставка в конец списка }

End;

Замечания.

1. Обратите внимание, что Pascal допускает многократное применение операции ^(разыменование) в одном выражении, что позволяет, имея указатель на какой-либо узел, обращаться к полям нескольких соседних узлов, продвигаясь по ссылкам. Такая «косвенная адресация» к различным элементам списка является удобным средством обработки.

2. Часто для ускорения доступа к элементам 2-связного списка его снабжают еще одним указателем h2 на конец списка.

3. В операциях с 2-связными списками удается избавиться от рабочего указателя pна предыдущий элемент.

4. На основе рассмотренных операций над списками можно сделать прос­тые и важные выводы. Если имеется последовательность элементов одного типа, то пред­ставление ее в виде списка особенно удобно в тех ситуациях, когда часто должны выполняться операции удаления и/или вставки произвольных элементов последовательности и когда использу­ется прохождение всего списка. Массивы и файлы, безусловно, хуже списков, если рассматривать операции удаления и/или вставки произволь­ных элементов. Для массивов требуется смеще­ние элементов, а для фай­лов — перезапись. Последовательная обработка массивов происходит не­сколько быстрее, чем последовательная обработка спи­сков, а последова­тельная обработка файлов — медленнее. Массивы имеют определен­ные пре­имущества перед списками при произвольном доступе к элемен­там, осо­бенно эффективен поиск определенного элемента в упорядочен­ном масси­ве. Этот тип поиска в случае списков относится к очень медленному и тре­бует в среднем п/2 обращений к элементам списка и сравнений. Если ожи­да­ется, что элементы будут выбираться из середины или конца списка, то не требу­ется его последовательно просматривать, а нужно хранить несколь­ко указателей на эти части списка.

Стек — частный случай линейного односвязного списка, для которого разрешено добавлять или удалять элементы только с одного конца списка, который называется вершиной стека (рис. 5.2). Такой принцип доступа к данным называется LIFO (Last In First Out – «последним пришел – первым вышел»). Голову списка в данном случае называют еще указателем стека (stack pointer –sp, однако в целях общности будем как и прежде придерживаться обозначения h).

Стек имеет важное значение для организации межмодульного взаимодействия, ор­ганизации прерываний, рекурсивных вычислений и еще много других полез­ных применений, с которыми мы позна­комимся в ходе изуче­ния различных алгоритмов.

Удобно все опера­ции со стеком офор­мить в виде процедур и функций и помес­тить в отдельный модуль. Ниже приводится пример такого модуля, в котором информационное поле элемента стека относится к символьному типу. Если нужен стек с другим типом элементов, то в этот модуль необходимо внести соответствующие измене­ния.

UNIT Stack;

Typeu = ^Uzl;

Uzl = Record

i :Char; {информационное поле символьного типа }

L :u;

End;

{ далее h – формальный параметр ! }

Procedure Push ( Var h :u; a :Char ); { включение в стек нового элемента.}

FunctionPop ( Var h :u ) :Char; {исключение элемента из стека }

FunctionEmpty ( h :u ) :Boolean; {функция «пустой» стек}

Function Top ( h :u ) :Char; {функция возвращает копию вершины}