Interface

Стек.

End

End

Then

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

End

End

Then

Begin

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

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

Type u = ^Uzl;

Uzl = Record

i:Integer;

L, R:u;

End;

Var h: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;

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

Var t:u;

t:= h;

While t <> Nil Do

If t^.i = a

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

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

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

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

Dispose(t); Exit;

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

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

End;

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

Var t, s:u;

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

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

If a <= t^.i

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

Then Begin s^.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;

Type u = ^Uzl;

Uzl = Record

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

L:u;

End;

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

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

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

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

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

Дата добавления: 2014-01-11