ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ

 

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ

Связное представление данных в памяти

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

Связные линейные списки

ременного числа элементов, к которым применимы операции включе- ния, исключения. Список, отражающий отношения соседства между элементами, называется линейным. Логические списки мы уже расс-

Машинное представление связных линейных списков

поле INF - информационное поле, данные, NEXT - указатель на сле- дующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который

Реализация операций над связными линейными списками

ми списками. Выполнение операций иллюстрируется в общем случае рисунками со схемами изменения связей и программными примерами. На всех рисунках сплошными линиями показаны связи, имевшиеся

Применение линейных списков

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

Мультисписки

структуры, могут решаться разные подзадачи, каждая из которых требует, возможно, обработки не всего множества объектов, а лишь какого-то его подмножества. Так, например, в автоматизированной

Нелинейные разветвленные списки

Основные понятия

Нелинейным разветвленным списком является список, элементами

которого могут быть тоже списки. В разделе 5.2 мы рассмотрели

двухсвязные линейные списки. Если один из указателей каждого эле-

мента списка задает порядок обратный к порядку, устанавливаемому

другим указателем, то такой двусвязный список будет линейным. Ес-

ли же один из указателей задает порядок произвольного вида, не

являющийся обратным по отношению к порядку, устанавливаемому дру-

гим указателем, то такой список будет нелинейным.

В обработке нелинейный список определяется как любая после-

довательность атомов и списков (подсписков), где в качестве атома

берется любой объект, который при обработке отличается от списка

тем, что он структурно неделим.

Если мы заключим списки в круглые скобки, а элементы списков

разделим запятыми, то в качестве списков можно рассматривать та-

кие последовательности:

(a,(b,c,d),e,(f,g))

( )

((a))

Первый список содержит четыре элемента: атом a, список (b,c,

d) (содержащий в свою очередь атомы b,c,d), атом e и список

(f,g), элементами которого являются атомы f и g. Второй список не

содержит элементов, тем не менее нулевой список, в соответствии с

нашим определением является действительным списком. Третий список

состоит из одного элемента: списка (a), который в свою очередь

содержит атом а.

Другой способ представления, часто используемый для иллюст-

рации списков, - графические схемы, аналогичен способу представ-

ления, применяемому при изображении линейных списков. Каждый эле-

мент списка обозначается прямоугольником; стрелки или указатели

показывают, являются ли прямоугольники элементами одного и того

же списка или элементами подсписка. Пример такого представления

дан на рис.5.12.

 

┌───┐ ┌────>┌───┐ ┌────>┌───┐ ┌────>┌───┐

│ a │ │ ┌─┼─ │ │ │ e │ │ ┌──┼─ │

├───┤ │ │ ├───┤ │ ├───┤ │ │ ├───┤

│ ─┼───┘ │ │ ─┼───┘ │ ─┼───┘ │ │nil│

└───┘ │ └───┘ └───┘ │ └───┘

└─>┌───┐ ┌>┌───┐ ┌>┌───┐ └─>┌───┐ ┌>┌───┐

│ b │ │ │ c │ │ │ d │ │ f │ │ │ g │

├───┤ │ ├───┤ │ ├───┤ ├───┤ │ ├───┤

│ ─┼──┘ │ ─┼──┘ │nil│ │ ─┼──┘ │nil│

└───┘ └───┘ └───┘ └───┘ └───┘

Рис.5.12. Схематическое представление разветвленного списка

Разветвленные списки описываются тремя характеристиками: по-

рядком, глубиной и длиной.

Порядок. Над элементами списка задано транзитивное отноше-

ние, определяемое последовательностью, в которой элементы появля-

ются внутри списка. В списке (x,y,z) атом x предшествует y, а y

предшествует z. При этом подразумевается, что x предшествует z.

Данный список не эквивалентен списку (y,z,x). При представлении

списков графическими схемами порядок определяется горизонтальными

стрелками. Горизонтальные стрелки истолковываются следующим обра-

зом: элемент из которого исходит стрелка,предшествует элементу,

на который она указывает.

Глубина. Это максимальный уровень, приписываемый элементам

внутри списка или внутри любого подсписка в списке. Уровень эле-

мента предписывается вложенностью подсписков внутри списка,

т.е.числом пар круглых скобок, окаймляющих элемент. В списке,

изображенном на рис.5.12), элементы a и e находятся на уровне 1,

в то время как оставшиеся элементы - b, c, d, f и g имеют уровень

2. Глубина входного списка равна 2. При представлении списков

схемами концепции глубины и уровня облегчаются для понимания, ес-

ли каждому атомарному или списковому узлу приписать некоторое

число l. Значение l для элемента x, обозначаемое как l(x), явля-

ется числом вертикальных стрелок, которое необходимо пройти для

того, чтобы достичь данный элемент из первого элемента списка. На

рис.5.12 l(a)=0, l(b)=1 и т.д. Глубина списка является максималь-

ным значением уровня среди уровней всех атомов списка.

Длина - это число элементов уровня 1 в списке. Например,

длина списка на рис.5.12 равна 3.

Типичный пример применения разветвленного списка - представ-

ление последнего алгебраического выражения в виде списка. Алгеб-

раическое выражение можно представить в виде последовательности

элементарных двухместных операций вида:

<операнд 1> <знак операции> <операнд 2>

┌───┐ ┌>┌───┐ ┌>┌───┐

┌─┼─ │ │ │ + │ │ │ f │

│ ├───┤ │ ├───┤ │ ├───┤

│ │ ─┼──┘ │ ─┼──┘ │nil│

│ └───┘ └───┘ └───┘

└>┌───┐ ┌>┌───┐ ┌──>┌───┐

┌───┼─ │ │ │ * │ │ ┌─┼─ │

│ ├───┤ │ ├───┤ │ │ ├───┤

│ │ ─┼──┘ │ ─┼──┘ │ │nil│

│ └───┘ └───┘ │ └───┘

└>┌───┐┌>┌───┐┌>┌───┐ └>┌───┐┌>┌───┐┌───>┌───┐

│ a ││ │ + ││ │ b │ │ c ││ │ - ││ ┌─┼─ │

├───┤│ ├───┤│ ├───┤ ├───┤│ ├───┤│ │ ├───┤

│ ─┼┘ │ ─┼┘ │nil│ │ ─┼┘ │ ─┼┘ │ │nil│

└───┘ └───┘ └───┘ └───┘ └───┘ │ └───┘ │

┌──────────────┘

└─>┌───┐┌>┌───┐┌>┌───┐

│ d ││ │ / ││ │ e │

├───┤│ ├───┤│ ├───┤

│ ─┼┘ │ ─┼┘ │nil│

└───┘ └───┘ └───┘

 

Рис.5.13. Схема списка, представляющего алгебраическое выражение

Выражение:

(a+b)*(c-(d/e))+f

будет вычисляться в следующем порядке:

a+b

d/e

c-(d/e)

(a+b)*(c-d/e)

(a+b)*(c-d/e)+f

При представлении выражения в виде разветвленного списка

каждая тройка "операнд-знак-операнд" представляется в виде спис-

ка, причем, в качестве операндов могут выступать как атомы - пе-

ременные или константы, так и подсписки такого же вида. Скобочное

представление нашего выражения будет иметь вид:

(((a,+,b),*,(c,-,(d,/,e)),+,f)

Глубина этого списка равна 4, длина - 3.

 

Представление списковых структур в памяти.

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

Операции обработки списков

Базовыми операциями при обработке списков являются операции

(функции): car, cdr, cons и atom.

Операция car в качестве аргумента получает список (указатель

на начало списка). Ее возвращаемым значением является первый эле-

мент этого списка (указатель на первый элемент). Например:

- если X - список (2,6,4,7), то car(X) - атом 2;

- если X - список ((1,2),6), то car(X) - список (1,2);

- если X - атом то car(X) не имеет смысла и в действитель-

ности не определено.

Операция cdr в качестве аргумента также получает список. Ее

возвращаемым значением является остаток списка - указатель на

список после удаления из него первого элемента. Например:

- если X - (2,6,4), то cdr(X) - (6,4);

- если X - ((1,2),6,5), то cdr(X) - (6,5);

- если список X содержит один элемент, то cdr(X) равно nil.

Операция cons имеет два аргумента: указатель на элемент

списка и указатель на список. Операция включает аргумент-элемент

в начало аргумента-списка и возвращает указатель на получившийся

список. Например:

- если X - 2, а Y - (6,4,7), то cons(X,Y) - (2,6,4,7);

- если X - (1,2), Y - (6,4,7), то cons(X,Y) - ((1,2),6,4,7).

Операция atom выполняет проверку типа элемента списка. Она

должна возвращать логическое значение: true - если ее аргумент

является атомом или false - если ее аргумент является подсписком.

В программном примере 5.11 приведена реализация описанных

операций как функций языка PASCAL. Структура элемента списка, об-

рабатываемого функциями этого модуля определена в нем как тип

litem и полностью соответствует рис.5.16. Помимо описанных опера-

ций в модуле определены также функции выделения памяти для деск-

риптора данных - NewAtom и для элемента списка - NewNode. Реали-

зация операций настолько проста, что не требует дополнительных

пояснений.

{==== Программный пример 5.11 ====}

{ Элементарные операции для работы со списками }

Unit ListWork;

Interface

type lpt = ^litem; { указатель на элемент списка }

litem = record

typeflg : char; { Char(0) - узел, иначе - код типа }

down : pointer; { указатель на данные или на подсписок }

next: lpt; { указатель на текущем уровне }

end;

Function NewAtom(d: pointer; t : char) : lpt;

Function NewNode(d: lpt) : lpt;

Function Atom(l : lpt) : boolean;

Function Cdr(l : lpt) : lpt;

Function Car(l : lpt) : lpt;

Function Cons(l1, l : lpt) : lpt;

Function Append(l1,l : lpt) : lpt;

Implementation

{*** создание дескриптора для атома }

Function NewAtom(d: pointer; t : char) : lpt;

var l : lpt;

begin New(l);

l^.typeflg:=t; { тип данных атома }

l^.down:=d; { указатель на данные }

l^.next:=nil; NewAtom:=l;

end;

{*** создание элемента списка для подсписка }

Function NewNode(d: lpt) : lpt;

var l : lpt;

begin

New(l);

l^.typeflg:=Chr(0); { признак подсписка }

l^.down:=d; { указатель на начало подсписка }

l^.next:=nil;

NewNode:=l;

end;

{*** проверка элемента списка: true - атом, false - подсписок }

Function Atom(l : lpt) : boolean;

begin { проверка поля типа }

if l^.typeflg=Chr(0) then Atom:=false

else Atom:=true;

end;

Function Car(l : lpt) : lpt; {выборка 1-го элемента из списка }

begin Car:=l^.down; { выборка - указатель вниз } end;

Function Cdr(l : lpt) : lpt;{исключение 1-го элемента из списка}

begin Cdr:=l^.next; { выборка - указатель вправо } end;

{*** добавление элемента в начало списка }

Function Cons(l1,l : lpt) : lpt;

var l2 : lpt;

begin l2:=NewNode(l1); { элемент списка для добавляемого }

l2^.next:=l; { в начало списка }

Cons:=l2; { возвращается новое начало списка }

end;

{*** добавление элемента в конец списка }

Function Append(l1,l : lpt) : lpt;

var l2, l3 : lpt;

begin

l2:=NewNode(l1); { элемент списка для добавляемого }

{ если список пустой - он будет состоять из одного эл-та }

if l=nil then Append:=l2

else begin { выход на последний эл-т списка }

l3:=l; while l3^.next<>nil do l3:=l3^.next;

l3^.next:=l2; { подключение нового эл-та к последнему }

Append:=l; { функция возвращает тот же указатель }

end; end;

END.

В примере 5.11 в модуль базовых операций включена функция

Append - добавления элемента в конец списка. На самом деле эта

операция не является базовой, она может быть реализована с ис-

пользованием описанных базовых операций, без обращения к внутрен-

ней структуре элемента списка, хотя, конечно, такая реализация

будет менее быстродействующей. В программном примере 5.12 приве-

дена реализация нескольких простых функций обработки списков, ко-

торые могут быть полезными при решении широкого спектра задач.

В функциях этого модуля, однако, не используется внутренняя

структура элемента списка.

{==== Программный пример 5.12 ====}

{ Вторичные функции обработки списков }

Unit ListW1;

Interface

uses listwork;

Function Append(x, l : lpt) : lpt;

Function ListRev(l, q : lpt) : lpt;

Function FlatList(l, q : lpt) : lpt;

Function InsList(x, l : lpt; m : integer) : lpt;

Function DelList(l : lpt; m : integer) : lpt;

Function ExchngList(l : lpt; m : integer) : lpt;

Implementation

{*** добавление в конец списка l нового элемента x }

Function Append(x, l : lpt) : lpt;

begin

{ если список пустой - добавить x в начало пустого списка }

if l=nil then Append:=cons(x,l)

{ если список непустой

- взять тот же список без 1-го эл-та - cdr(l);

- добавить в его конец эл-т x;

- добавить в начало 1-й эл-т списка }

else Append:=cons(car(l),Append(x,cdr(l)));

end; { Function Append }

{*** Реверс списка l; список q - результирующий, при первом

вызове он должен быть пустым }

Function ListRev(l, q : lpt) : lpt;

begin

{ если входной список исчерпан, вернуть выходной список }

if l=nil then ListRev:=q

{ иначе: - добавить 1-й эл-т вх.списка в начало вых.списка,

- реверсировать, имея вх. список без 1-го эл-та,

а вых.список - с добавленным эл-том }

else ListRev:=ListRev(cdr(l),cons(car(l),q));

end; { Function ListRev }

{*** Превращение разветвленного списка l в линейный; список q -

результирующий, при первом вызове он должен быть пустым }

Function FlatList(l, q : lpt) : lpt;

begin

{ если входной список исчерпан, вернуть выходной список }

if l=nil then FlatList:=q

else

{ если 1-й эл-т вх. списка - атом, то

- сделать "плоской" часть вх. списка без 1-го эл-та;

- добавить в ее начало 1-й эл-т }

if atom(car(l)) then

FlatList:=cons(car(l),FlatList(cdr(l),q))

{ если 1-й эл-т вх. списка - подсписок, то

- сделать "плоской" часть вх.списка без 1-го эл-та;

- сделать "плоским" подсписок 1-го эл-та }

else FlatList:=FlatList(car(l),FlatList(cdr(l),q));

end; { Function FlatList }

{*** вставка в список l элемента x на место с номером m

( здесь и далее нумерация эл-тов в списке начинается с 0 ) }

Function InsList(x, l : lpt; m : integer) : lpt;

begin

{ если m=0, эл-т вставляется в начало списка }

if m=0 then InsList:=cons(x,l)

{ если список пустой, он и остается пустым }

else if l=nil then InsList:=nil

{ - вставить эл-т x на место m-1 в список без 1-го эл-та;

- в начало полученного списка вставить 1-й эл-т }

else InsList:=cons(car(l),InsList(x,cdr(l),m-1));

end; { Function InsList }

{*** удаление из списка l на месте с номером m }

Function DelList(l : lpt; m : integer) : lpt;

begin

{ если список пустой, он и остается пустым }

if l=nil then DelList:=nil

{ если m=0, эл-т удаляется из начала списка }

else if m=0 then DelList:=cdr(l)

{ - удалить эл-т x на месте m-1 в список без 1-го эл-та;

- в начало полученного списка вставить 1-й эл-т }

else DelList:=cons(car(l),DelList(cdr(l),m-1));

end; { Function DelList }

{*** перестановка в списке l эл-тов местах с номерами m и m+1 }

Function ExchngList(l : lpt; m : integer) : lpt;

begin { если список пустой, он и остается пустым }

if l=nil then ExchngList:=nil

else if m=0 then

{если m=0, а следующего эл-та нет, список остается без изменений}

if cdr(l)=nil then ExchngList:=l

{ если m=0 ( обмен 0-го и 1-го эл-тов):

- берется список без двух 1-ых эл-тов - cdr(cdr(l));

- в его начало добавляется 0-й эл-т;

- в начало полученного списка добавляется 1-й эл-т - car(cdr(l))}

else ExchngList:= cons(car(cdr(l)),cons(car(l),cdr(cdr(l))))

else ExchngList:=cons(car(l),ExchngList(cdr(l),m-1));

end; { Function ExchngList }

END.

Для облегчения читателю задачи самостоятельного исследования

примера первые две его функции мы разберем подробно. Поскольку в

функциях этого примера широко используются вложенные вызовы, в

том числе и рекурсивные, в нижеследующих разборах описание каждо-

го следующего вложенного вызова сдвигается вправо.

Функция Append добавляет элемент x в конец списка l. Расс-

мотрим ее выполнение на примере вызова: Append(4,(1,2,3)).

Поскольку аргумент-список не пустой, выполняется ветвь else.

Она содержит оператор:

Append:=cons(car(l),Append(x,cdr(l)));

Важно точно представить себе последовательность действий по

выполнению этого оператора:

- car(l) = 1;

- cdr(l) = (2,3);

- Append(4,(2,3))) - при этом рекурсивном вызове выполнение

вновь пойдет по ветви else, в которой:

- car(l) = 2;

- cdr(l) = (3);

- Append(4,(3))) - выполнение вновь пойдет по ветви else,

в которой:

- car(l) = 3;

- cdr(l) = nil;

- Append(4,nil) - в этом вызове список-аргумент пустой, по-

этому выполнится Append:=cons(4,nil) и вызов вернет список: (4);

- cons(car(l),Append(x,cdr(l))) - значения аргументов

функции cons - для этого уровня вызовов: cons(3,(4)) = (3,4);

- на этом уровне Append возвращает список (3,4);

- cons(car(l),Append(x,cdr(l))) - на этом уровне: cons(2,

(3,4)) = (2,3,4);

- на этом уровне Append возвращает список (2,3,4);

- cons(car(l),Append(x,cdr(l))) - на этом уровне: cons(1,

(2,3,4)) = (1,2,3,4);

- на этом уровне Append возвращает список (1,2,3,4).

Функция ListRev выполняет инвертирование списка - изменения

порядка следования его элементов на противоположный. При обраще-

нии к функции ее второй аргумент должен иметь значение nil. При-

мер: ListRev(1,(2,3),4),nil).

Входной список не пустой, поэтому выполнение идет по ветви

else, где:

ListRev:=ListRev(cdr(l),cons(car(l),q));

Последовательность действий:

- cdr(l) = ((2,3),4);

- car(l) = 1;

- cons(car(l),q) = (1) - список q при этом - пустой;

- рекурсивный вызов ListRev( ((2,3),4), (1)):

- cdr(l) = (4);

- car(l) = (2,3);

- cons(car(l),q) = ((2,3),1) - список q - (1);

- рекурсивный вызов ListRev((4), ((2,3),1)):

- cdr(l) = nil;

- car(l) = 4;

- cons(car(l),q) = (4,(2,3),1);

- рекурсивный вызов ListRev(nil, (4,(2,3),1)):

- поскольку исходный список пустой, вызов возвраща-

ет список: (4,(2,3),1);

- вызов возвращает список: (4,(2,3),1);

- вызов возвращает список: (4,(2,3),1);

- вызов возвращает список: (4,(2,3),1).

В программном примере 5.13 применение ветвящихся списков по-

казано для решения более прикладной задачи. Представленная здесь

программа - калькулятор, она вычисляет значение введенного ариф-

метического выражения, составляющими которого могут быть целые

числа, знаки четырех арифметических операций и круглые скобки.

Для упрощения примера мы ввели следующие ограничения:

- вся арифметика - целочисленная;

- программа не проверяет правильность исходной записи;

- в выражении не допускается унарный минус.

{==== Программный пример 5.13 ====}

{ Калькулятор. Вычисление арифметических выражений }

program Calc;

Uses ListWork;

type cptr = ^char;

iptr = ^ integer;

const { цифровые символы }

digits : set of char = ['0'..'9'];

{ знаки операций с высоким приоритетом }

prty : set of char = ['*','/'];

var s : string; { исходная строка }

n : integer; { номер текущего символа в исх. строке }

{*** Представление исходной строки в списочной форме }

Function Creat_Lst : lpt;

 

- 171 -

var lll : lpt; { указатель на начало текущего списка }

s1 : char; { текущий символ строки }

st : string; { накопитель строки-операнда }

{* Создание атома для Integer }

Procedure NewInt;

var ip : iptr; cc : integer;

begin

if Length(st)>0 then begin

{ если в st накоплено цифровое представление числа, оно

переводится в тип integer, для него создается атом и

записывается в конец списка }

New(ip); Val(st,ip^,cc);

lll:=Append(NewAtom(ip,'I'),lll);

st:=''; { накопитель строки сбрасывается }

end; end; { Procedure NewInt }

Procedure NewChar; { Создание атома для Char }

var cp : cptr;

begin { выделяется память для 1 символа, в ней сохраняется

значение s1,для него создается атом, записывается в конец списка}

New(cp); cp^:=s1;

lll:=Append(NewAtom(cp,'C'),lll);

end; { Procedure NewChar }

begin { Function Creat_Lst }

{ исходный список пустой, накопитель строки - пустой }

lll:=nil; st:='';

while n<=length(s) do begin { цикл до конца исходной строки }

s1:=s[n]; n:=n+1;

case s1 of

'(' : { начало скобочного подвыражения: для него создается

новый список - Creat_Lst, который оформляется как под-

список - NewNode и добавляется в конец текущего

списка - Append }

lll:=Append(NewNode(Creat_Lst),lll);

')' : { конец скобочного выражения - последнее число в

скобках добавляется в конец текущего списка и текущий

список сформирован - конец функции }

begin

NewInt; Creat_Lst:=lll; Exit;

end;

else {begin} { цифра или знак операции }

if s1 in Digits then { цифры накапливаются в st }

st:=st+s1

else begin { знак операции }

NewInt; { созд. атом для ранее накопленного числа }

NewChar; { созд. атом для знака }

end; { end;} end; { case } end; { while }

NewInt; { созд. атом для ранее накопленного числа }

Creat_Lst:=lll;

end; { Function Creat_Lst }

{*** Выделение в подсписки высокоприоритетных операций }

Function FormPrty(l : lpt) : lpt;

var op1, op, op2 : lpt; { 1-й операнд, знак, 2-й операнд }

l2,l3 : lpt;

cp: ^char;

begin

l2:=nil; { выходной список пустой }

{ выделение 1-го операнда }

op1:=car(l); l:=cdr(l);

{ если 1-й операнд - подсписок - обработка подсписка }

if not atom(op1) then op1:=FormPrty(op1);

while l<>nil do begin { до опустошения исходного списка }

{ выделение знака операции }

op:=car(l); l:=cdr(l);

{ выделение 2-го операнда }

op2:=car(l); l:=cdr(l);

{ если 2-й операнд - подсписок - обработка подсписка }

if not atom(op2) then op2:=FormPrty(op2);

if cptr(op^.down)^ in prty then

{ если знак операции приоритетный, то создается подспи-

сок: 1-й операнд, знак, 2-й операнд, этот подсписок

далее является 1-ым операндом }

op1:=cons(op1,cons(op,cons(op2,nil)))

else begin { если знак неприоритетный, 1-й операнд и знак

записываются в выходной список, 2-й операнд далее

является 1-ым операндом }

l2:=Append(op,Append(op1,l2));

op1:=op2;

end; end;

FormPrty:=Append(op1,l2); { последний операнд добавляется в

выходной список }

end; { Function FormPrty }

{*** Вычисление выражения }

Function Eval(l : lpt) : integer;

var op1, op, op2 : lpt;

begin

{ выделение 1-го операнда }

op1:=car(l); l:=cdr(l);

{ если 1-й операнд - подсписок - вычислить его выражение }

if not atom(op1) then iptr(op1^.down)^:=Eval(op1);

while l<>nil do begin

{ выделение знака операции }

op:=car(l); l:=cdr(l);

{ выделение 2-го операнда }

op2:=car(l); l:=cdr(l);

{ если 2-й операнд - подсписок - вычислить его выражение }

if not atom(op2) then iptr(op2^.down)^:=Eval(op2);

{ выполнение операции, результат - в op1 }

case cptr(op^.down)^ of

'+' : iptr(op1^.down)^:=iptr(op1^.down)^+iptr(op2^.down)^;

'-' : iptr(op1^.down)^:=iptr(op1^.down)^-iptr(op2^.down)^;

'*' : iptr(op1^.down)^:=iptr(op1^.down)^*iptr(op2^.down)^;

'/' : iptr(op1^.down)^:=iptr(op1^.down)^ div iptr(op2^.down)^;

end;

end;

Eval:=iptr(op1^.down)^; { возврат последнего результата }

end; { Function Eval }

{*** Главная программа }

var l : lpt;

begin

write('>'); readln(s); { ввод исходной строки }

{ формирование списка }

n:=1; l:=Creat_Lst;

{ выделение приоритетных операций }

l:=FormPrty(l);

{ вычисление и печать результата }

writeln(s,'=',Eval(l));

END.

Выполнение программы состоит во вводе строки, представляющей

исходное выражение и последовательных обращений к трем функциям:

Creat_Lst, FormPrty и Eval.

Функция Creat_Lst преобразует исходную строку в список. В

функции поэлементно анализируются символы строки. Различаемые

символы: левая круглая скобка, правая скобка, знаки операций и

цифры. Цифровые символы накапливаются в промежуточной строке.

Когда встречается символ-разделитель - правая скобка или знак

операции накопленная строка преобразуется в число, для него соз-

дается атом с типом 'I' и включается в конец списка. Для знака

операции создается атом с типом 'C' и тоже включается в конец

списка. Левая скобка приводит к рекурсивному вызову Creat_Lst.

Этот вызов формирует список для подвыражения в скобках, формиро-

вание списка заканчивается при появлении правой скобки. Для сфор-

мированного таким образом списка создается узел, и он включается

в основной список как подсписок. Так, например, для исходной

строки:

5+12/2-6*(11-7)+4

функцией Creat_Lst будет сформирован такой список:

(5,+,12,/,2,-,6,*,(11,-,7),+,4)

Следующая функция - FormPrty - выделяет в отдельные подспис-

ки операции умножения и деления, имеющие более высокий приоритет,

и их операнды. Функция просматривает список и выделяет в нем пос-

ледовательные тройки элементов "операнд-знак-операнд". Если один

из операндов является подсписком, то он обрабатывается функцией

FormPrty. Если знак является одним из приоритетных знаков, то из

тройки формируется подсписок, который становится первым операндом

для следующей тройки. Если знак не приоритетный, то второй опе-

ранд тройки становится первым для следующей тройки. Список нашего

примера после обработки его функцией FormPrty превратится в:

(5,+,(12,/,2),-,(6,*,(11,-,7)),+,4)

Наконец, функция Eval выполняет вычисления. Она во многом

похожа на функцию FormPrty: в ней также выделяются тройки "опе-

ранд 1- 0знак-операнд". Если один или оба операнда являются подспис-

ками, то сначала вычисляются эти подсписки и заменяются на атомы

- результаты вычисления. Если оба операнда - атомы, то над ними

выполняется арифметика, задаваемая знаком операции. Поскольку в

первую очередь вычисляются подсписки, то подвыражения, обозначен-

ные скобками в исходной строке, и операции умножения и деления вы-

полняются в первую очередь. Для нашего примера порядок вычислений

будет таков:

12 / 2 = 6; 5 + 6 = 11; 11 - 7 = 4; 6 * 4 = 24;

24 + 4 = 28; 11 - 28 = -17

 

5.5. Язык программирования LISP

LISP является наиболее развитым и распространенным языком

обработки списков. "Идеология" и терминология этого языка в зна-

чительной степени повлияла на общепринятые подходы к обработке

списков и использовалась и нами в предыдущем изложении. Все дан-

ные в LISP представляются в виде списков, структура элемента

списка соответствует рис.5.15. LISP обеспечивает базовые функции

обработки списков - car, cdr, cons, atom. Также многие вторичные

функции реализованы в языке как базовые - для повышения их эффек-

тивности. Помимо чисто списковых операций в языке обеспечиваются

операции для выполнения арифметических, логических операций, от-

ношения, присваивания, ввода-вывода и т.д. Операция cond обеспе-

чивает ветвление.

Сама LISP-программа представляется как список, записанный в

скобочной форме. Элементами простого программного списка является

имя операции/функции и ее параметры. Параметрами могут быть в

свою очередь обращения к функциям, которые образуют подсписки.

Как правило, вся программа на LISP представляет собой единствен-

ное обращение к функции с множеством вложенных обращений - рекур-

сивных или к другим функциям. Поэтому программирование на языке

LISP часто называют "функциональным программированием". Функции,

приведенные нами в примере 5.11 являются переложением на язык

PASCAL их LISP-реализаций.

Системы программирования LISP строятся и как компиляторы, и

как интерпретаторы. Однако, независимо от подхода к построению

системы программирования, она обязательно включает в себя "сборку

мусора" (см.раздел 5.7). Обратите внимание на то, что в примере

5.11, представляя PASCAL-реализацию операций языка LISP, мы в не-

которых функциях выделяли память, но нигде ее не освобождали.

Система программирования LISP автоматически следит за использова-

нием памяти и обеспечивает ее освобождение.

Другие языки обработки списков, например IPL-V, COMMIT в

большей мере ориентированы на решение прикладных задач, а не на

обработку абстрактных списков, хотя использование списковых

структур заложено в основы в их реализации.

 

5.6. Управление динамически выделяемой памятью

Динамические структуры по определению характеризуется непос-

тоянством и непредсказуемостью размера. Поэтому память под от-

дельные элементы таких структур выделяется в момент, когда они

"начинают существовать" в процессе выполнения программы, а не

вовремя трансляции. Когда в элементе структуры больше нет необхо-

димости, занимаемая им память освобождается.

В современных вычислительных средах большая часть вопросов,

связанных с управлением памятью решается операционными системами

или системами программирования. Для программиста прикладных задач

динамическое управление памятью либо вообще прозрачно, либо осу-

ществляется через достаточно простой и удобный интерфейс стан-

дартных процедур/функций. Однако, перед системным программистом

вопросы управления памятью встают гораздо чаще. Во-первых, эти

вопросы в полном объеме должны быть решены при проектировании

операционных систем и систем программирования, во-вторых, некото-

рые сложные приложения могут сами распределять память в пределах

выделенного им ресурса, наконец в-третьих, знание того, как в

данной вычислительной среде распределяется память, позволит прог-

раммисту построить более эффективное программное изделие даже при

использовании интерфейса стандартных процедур.

В общем случае при распределении памяти должны быть решены

следующие вопросы:

- способ учета свободной памяти;

- дисциплины выделения памяти по запросу;

- обеспечение утилизации освобожденной памяти.

В распоряжении программы обычно имеется адресное пространс-

тво, которое может рассматриваться как последовательность ячеек

памяти с адресами, линейно возрастающими от 0 до N. Какие-то час-

ти этого адресного пространства обычно заняты системными програм-

мами и данными, какие-то - кодами и статическими данными самой

программы, оставшаяся часть доступна для динамического распреде-

ления. Обычно доступная для распределения память представляет со-

бой непрерывный участок пространства с адресными границами от n1

до n2. В управлении памятью при каждом запросе на память необхо-

димо решать, по каким адресам внутри доступного участка будет

располагаться выделяемая память.

В некоторых системах программирования выделение памяти авто-

матизировано полностью: система не только сама определяет адрес

выделяемой области памяти, но и определяет момент, когда память

должна выделяться. Так, например, выделяется память под элементы

списков в языке LISP, под символьные строки в языках SNOBOL и

REXX. В других системах программирования - к ним относится боль-

шинство универсальных процедурных языков программирования - мо-

менты выделения и освобождения памяти определяются программистом.

Программист должен выдать запрос на выделение/освобождение памяти

при помощи стандартной процедуры/функции - ALLOCATE/FREE в PL/1,

malloc/free в C, New/Dispose в PASCAL и т.п. Система сама опреде-

ляет размещение выделяемого блока и функция выделения памяти

возвращает его адрес. Наконец, в уже названных выше задачах сис-

темного программирования программист зачастую должен определить

также и адрес выделяемой области.

Память всегда выделяется блоками - т.е. обязательно непре-

рывными последовательностями смежных ячеек. Блоки могут быть фик-

сированной или переменной длины. Фиксированный размер блока го-

раздо удобнее для управления: в этом случае вся доступная для

распределения память разбивается на "кадры", размер каждого из

которых равен размеру блока, и любой свободный кадр годится для

удовлетворения любого запроса. К сожалению, лишь ограниченный

круг реальных задач может быть сведен к блокам фиксированной дли-

ны.

Одной из проблем, которые должны приниматься во внимание при

управлении памятью является проблема фрагментации (дробления) па-

мяти. Она заключается в возникновении "дыр" - участков памяти,

которые не могут быть использованы. Различаются дыры внутренние и

внешние. Внутренняя дыра - неиспользуемая часть выделенного бло-

ка, она возникает, если размер выделенного блока больше запрошен-

ного. Внутренние дыры характерны для выделения памяти блоками

фиксированной длины. Внешняя дыра - свободный блок, который в

принципе мог бы быть выделен, но размер его слишком мал для удов-

летворения запроса. Внешние дыры характерны для выделения блоками

переменной длины. Управление памятью должно быть построено таким

образом, чтобы минимизировать суммарный объем дыр.

Система управления памятью должна прежде всего "знать", ка-

кие ячейки имеющейся в ее распоряжении памяти свободны, а какие -

заняты. Методы учета свободной памяти основываются либо на прин-

ципе битовой карты, либо на принципе списков свободных блоков.

В методах битовой карты создается "карта" памяти - массив

бит, в котором каждый однобитовый элемент соответствует единице

доступной памяти и отражает ее состояние: 0 - свободна, 1 - заня-

та. Если считать единицей распределения единицу адресации - байт,

то сама карта памяти будет занимать 1/8 часть всей памяти, что

делает ее слишком дорогостоящей. Поэтому при применении методов

битовой карты обычно единицу распределения делают более крупной,

например, 16 байт. Карта, таким образом, отражает состояние

каждого 16-байтного кадра. Карта может рассматриваться как строка

бит, тогда поиск участка памяти для выделения выполняется как по-

иск в этой строке подстроки нулей требуемой длины.

В другой группе методов участки свободной памяти объединяют-

ся в связные списки. В системе имеется переменная, в которой хра-

нится адрес первого свободного участка. В начале первого

свободного участка записывается его размер и адрес следующего

свободного участка. В простейшем случае список свободных блоков

никак не упорядочивается. Поиск выполняется перебором списка.

Дисциплины выделения памяти решают вопрос: какой из свобод-

ных участков должен быть выделен по запросу. Выбор дисциплины

распределения не зависит от способа учета свободной памяти. Две

основные дисциплины сводятся к принципам "самый подходящий" и

"первый подходящий". По дисциплине "самый подходящий" выделяется

тот свободный участок, размер которого равен запрошенному или

превышает его на минимальную величину. По дисциплине "первый под-

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

которого не меньше запрошенного. При применении любой дисциплины,

если размер выбранного для выделения участка превышает запрос,

выделяется запрошенный объем памяти, а остаток образует свободный

блок меньшего размера. В некоторых системах вводится ограничение

на минимальный размер свободного блока: если размер остатка мень-

ше некоторого граничного значения, то весь свободный блок выделя-

ется по запросу без остатка. Практически во всех случаях дисцип-

лина "первый подходящий" эффективнее дисциплины "самый

подходящий". Это объясняется во-первых, тем, что при поиске пер-

вого подходящего не требуется просмотр всего списка или карты до

конца, во-вторых, тем, что при выборе всякий раз "самого подходя-

щего" остается больше свободных блоков маленького размера - внеш-

них дыр.

Когда в динамической структуре данных или в отдельном ее

элементе нет больше необходимости, занимаемая ею память должна

быть утилизована, т.е. освобождена и сделана доступной для нового

распределения. В тех системах, где память запрашивается програм-

мистом явным образом, она и освобождена должна быть явным обра-

зом. Даже в некоторых системах, где память выделяется автомати-

чески, она освобождается явным образом (например, операция DROP в

языке REXX). В таких системах, конечно, задача утилизации решает-

ся просто. При представлении памяти на битовой карте достаточно

просто сбросить в 0 биты, соответствующие освобожденным кадрам.

При учете свободной памяти списками блоков освобожденный участок

должен быть включен в список, но одного этого недостаточно. Сле-

дует еще позаботиться о том, чтобы при образовании в памяти двух

смежных свободных блоков они слились в один свободный блок сум-

марного размера. Задача слияния смежных блоков значительно упро-

щается при упорядочении списка свободных блоков по адресам памяти

- тогда смежные блоки обязательно будут соседними элементами это-

го списка.

Задача утилизации значительно усложняется в системах, где

нет явного освобождения памяти: тогда на систему ложится задача

определения того, какие динамические структуры или их элементы

уже не нужны программисту. Один из методов решения этой задачи

предполагает, что система не приступает к освобождению памяти до

тех пор, пока свободной памяти совсем не останется. Затем все за-

резервированные блоки проверяются и освобождаются те из них, ко-

торые больше не используются. Такой метод называется "сборкой му-

сора". Программа, сборки мусора вызывается тогда, когда нет

возможности удовлетворить некоторый частный запрос на память, или

когда размер доступной области памяти стал меньше некоторой зара-

нее определенной границы. Алгоритм сборки мусора обычно бывает

двухэтапным. На первом этапе осуществляется маркировка (пометка)

всех блоков, на которые указывает хотя бы один указатель. На вто-

ром этапе все неотмеченные блоки возвращаются в свободный список,

а метки стираются. Важно, чтобы в момент включения сборщика мусо-

ра все указатели были установлены на те блоки, на которые они

должны указывать. Если необходимо в некоторых алгоритмах приме-

нять методы с временным рассогласованием указателей, необходимо

временно отключить сборщик мусора - пока имеется такое рассогла-

сование. Один из самых серьезных недостатков метода сборки мусора

состоит в том, что расходы на него увеличиваются по мере уменьше-

ния размеров свободной области памяти.

Другой метод - освобождать любой блок, как только он перес-

тает использоваться. Он обычно реализуется посредством счетчиков

ссылок - счетчиков, в которых записывается, сколько указателей на

данный блок имеется в данный момент времени. Когда значение счет-

чика становится равным 0, соответствующий блок оказывается недос-

тупным и, следовательно, не используемым. Блок возвращается в

свободный список. Такой метод предотвращает накопление мусора, не

требует большого числа оперативных проверок во время обработки

данных. Однако и у этого метода есть определенные недостатки. Во-

первых, если зарезервированные блоки образуют циклическую струк-

туру, то счетчик ссылок каждого из них не равен 0, когда все свя-

зи, идущие извне блоков в циклическую структуру, будут

уничтожены. Это приводит к появлению мусора. Существуют различные

возможности устранить этот недостаток: запретить циклические и

рекурсивные структуры; отмечать циклические структуры флажками, и

обрабатывать их особым образом; потребовать, чтобы любая цикли-

ческая структура всегда имела головной блок, счетчик циклов кото-

рого учитывал бы только ссылки от элементов, расположенных вне

цикла, и чтобы доступ ко всем блокам этой структуры осуществлялся

только через него. Во-вторых, требуются лишние затраты времен и

памяти на ведение счетчиков ссылок.

В некоторых случаях может быть полезен метод восстановления

ранее зарезервированной памяти, называемый уплотнением. Уплотне-

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

целью сбора всех свободных блоков в один большой блок. Преиму-

щество этого метода в том, что после его применения выделение па-

мяти по запросам упрощается. Единственная серьезная проблема,

возникающая при использовании метода - переопределение указате-

лей. Механизм уплотнения использует несколько просмотров памяти.

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

рые были отмечены в предыдущем проходе, а затем во время следую-

щего просмотра памяти все указатели, связанные с отмеченными бло-

ками, переопределяются. После этого отмеченные блоки

переставляются. Механизма освобождения памяти в методе восстанов-

ления совсем нет. Вместо него используется механизм маркировки,

который отмечает блоки, используемые в данный момент. Затем,

вместо того, чтобы освобождать каждый не отмеченный блок путем

введения в действие механизма освобождения памяти, помещающего

этот блок в свободный список, используется уплотнитель, который

собирает неотмеченные блоки в один большой блок в одном конце об-

ласти памяти. Недостаток метода в том, что из-за трех просмотров

памяти велики затраты времени. Однако повышенная скорость резер-

вирования в определенных условиях может компенсировать этот не-

достаток.

Практическая эффективность методов зависит от многих пара-

метров, таких как частота запросов, статистическое распределение

размеров запрашиваемых блоков, способ использования системы -

групповая обработка или стратегия обслуживания при управлении вы-

числительным центром.