Главная Промышленная автоматика.

procedure DELETE { p: position; var i: LIST ); begin

if p = 0 then

move(L, available)

else

move{SPACE[p] .next, available) end; { DELETE }

procedure initialize

{ initialize связывает ячейки SPACE в один свободный список } var

i: integer begin

for i;= maxlength - 1 downto 1 do

SPACE[i] .next:= i + 1; available:= 1; SPACE [max length] .next:= 0

{ помечен конец свободного списка } end; { initialize }

Дважды связные списки

Во многих приложениях возникает необходимость организовать эффективное перемещение по списку как в прямом, так и в обратном направлениях. Или по заданному элементу нужно быстро найти предществующий ему и последующий элементы. В этих ситуациях можно дать каждой ячейке указатели и на следующую, и на предыдущую ячейки списка, т.е. организовать дважды связный список (рис. 2.7). В главе 12 будут приведены ситуации, когда использование дважды связных списков осо-бенноэффективно.

Рис. 2.7. Дважды связный список

Другое важное преимущество дважды связных списков заключается в том, что мы можем использовать указатель ячейки, содержащей i-й элемент, для определения i-й позиций - вместо использования указателя предшествующей ячейки. Но ценой этой возможности являются дополнительные указатели в каждой ячейке и определенное удлинение некоторых процедур, реализующих основные операторы списка. Если мы используем указатели (а не курсоры), то объявление ячеек, содержащих элементы списка и два указателя, можно выполнить следующим образом (previous - поле, содержащее указатель на предществую-щую ячейку):

type

celltype = record

element: elementtype; next, previous: t celltype

end;

position = t celltype;

Процедура удаления элемента в позиции р дважды связного списка показана в листинге 2.7. На рис. 2.8 Приведена схема удаления элемента в предположении, что



удаляемая ячейка не является ни первой, ни последней в списке. На этой схеме сплошными линиями показаны указатели до удаления, а пунктирными - после удаления элемента. В процедуре удаления сначала с помошью указателя поля previous определяется положение предыдушей ячейки. Затем в поле next этой (предыдушей) ячейки устанавливается указатель, указывающий на ячейку, следующую за позицией р. Далее подобным образом определяется следующая за позицией р ячейка и в ее поле previous устанавливается указатель на ячейку, предшествующую позиции р. Таким образом, ячейка в позиции р исключается из цепочек указателей и при необходимости может быть использована повторно.

Листинг 2.7. Удаление элемента из дважды связного списка

procedure DELETE { varp: position ) ; begin

if pt.previous <> nil then

{ удаление ячейки, которая не является первой } pt.previoust.next:= pt.next; if pt.next о nil then

{ удаление ячейки, которая не является последней pt.nextt.previous:= pt.previous end; { DELETE }

Рис.2.8. Схема удаления ячейки в дважды связном списке

2.3. Стеки

Стек - это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной (top). Стеки также иногда называют "магазинами", а в англоязычной литературе для обозначения стеков еще используется аббревиатура LIFO (last-in-first-out - последний вошел - первый вышел). Интуитивными моделями стека могут служить колода карт на столе при игре в покер, книги, сложенные в стопку, или стопка тарелок на полке буфета; во всех этих моделях взять можно только верхний предмет, а добавить новый объект можно, только положив его на верхний. Абстрактные типы данных семейства STACK (Стек) обычно используют следующие пять операторов.

1. MAKENULL(S). Делает стек S пустым.

2. TOP(S). Возвращает элемент из вершины стека S. Обычно вершина стека идентифицируется позицией 1, тогда TOP(S) можно записать в терминах общих операторов списка как RETRIEVE(FIRST(S), S).

3. POP(S). Удаляет элемент из вершины стека (выталкивает из стека), в терминах операторов списка этот оператор можно записать как DELETE(FIRST(S), S).

В этой связи отметим, что на практике обычно делают так, что ячейка заголовка два>иаы связного списка "замыкает круг" ячеек, т.е. указатель поля previous ячейки заголовка указывает на последнюю ячейку, а указатель поля next - на первую. Поэтому при такой реализации дважды связного списка нет необходимости в выполнении проверки на "нулевой указатель".



Иногда этот оператор реализуется в виде функции, возвращающей удаляемый элемент.

4. PUSH(a;, S). Вставляет элемент х в верщину стека S (заталкивает элемент в стек). Элемент, ранее находивщийся в верщине стека, становится элементом, следующим за верпхиной, и т.д. В терминах общих операторов списка данный оператор можно записать как INSERT(a;, FIRST(S), S).

5. EMPTY(S). Эта функция возвращает значение true (истина), если стек S пустой, и значение false (ложь) в противном случае.

Пример 2.2. Все текстовые редакторы имеют определенные символы, которые служат в качестве стирающих символов (erase character), т.е. таких, которые удаляют (стирают) символы, стоящие перед ними; эти символы "работают" как клавища <Backspace> на клавиатуре компьютера. Например, если символ # определен стирающим символом, то строка otic#d##e в действительности является строкой ас. Здесь первый символ # удаляет букву с, второй стирающий символ стирает букву d, а третий - букву Ъ.

Текстовые редакторы имеют также символ-убийцу (kill character), который удаляет все символы текущей строки, находящиеся перед ним. В этом примере в качестве символа-убийцы определим символ @.

Операции над текстовыми строками часто выполняются с использованием стеков. Текстовый редактор поочередно считывает символы, если считанный символ не является ни символом-убийцей, ни стирающим символом, то он помещается в стек. Если вновь считанный символ - стирающий символ, то удаляется символ в верщине стека. В случае, когда считанный символ является символом-убийцей, редактор очищает весь стек. В листинге 2.7 представлена программа, выполняющая описанные действия.

Листинг 2.7. Программа, реализующая действия стирающего символа и символа-убийцы

procedure EDIT; var

s: STACK; с: char; begin

MAKENULL(S); while not eoln do begin readic) ; if с = #• then

POP(S> else if с = @ then

MAKENULL (S) ; else { с - обычный символ } PURSH(c, S)

end;

печать содержимого стека S в обратном порядке end; { EDIT }

В этой программе тип STACK можно объявить как список символов. Процесс вывода содержимого стека в обратном порядке в последней строке программы требует небольщой хитрости. Выталкивание элементов из стека по одному за один раз в принципе позволяет получить последовательность элементов стека в обратном порядке. Некоторые реализации стеков, например с помощью массивов, как описано ни-

В этом листинге используется стандартная функция языка Pascal eoln, возвращающая значение true, если текущий символ - символ конна строки. - Прим. ред.





0 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0026