3345

Процедура В СТЕК и ИЗ СТЕКА описывается на АЛГОЛЕ

так:

procedure В СТЕК (S,x); value x, integer array S; integer x;

begin S[S[0]]:=x, S[0]:=S[0]+1 end

procedure ИЗ СТЕКА (S,x); value x, integer array S; integer x;

begin x:= S[S[0]-1], S[0]:=S[0]-1 end

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

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

Первый элемент блока - это указатель вершины стека, всегда указывающий на текущую вершину стека (см. рис. 3.11, с. 86).

141

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

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

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

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

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

143

других заказов, ожидающих выполнения. То есть в структуре очереди выполняются две операции:

-выборка и удаление из очереди первого ее элемента;

-занесение в конец очереди нового элемента.

Для их выполнения в ЯзПр создаются соответствующие процедуры. На языке АЛГОЛ они записываются так:

procedure В ОЧЕРЕДЬ (S,x) конец: (к); value x; integer array S; integer x, к; begin S[к]:=x, к:=к+1 end

procedure ИЗ ОЧЕРЕДИ (S,x) начало: (n); integer array S; integer x, n;

begin x:= S[n], n:=n+1 end

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

При выполнении второй процедуры указатель начала очереди n продвигается на единицу вперед. Если очередь пустая, n=к.

Структура памяти. Для очередей используется как последовательное, так и связанное представления. Как и в случае стеков последовательное представление требует резервирования блока памяти, внутри которого очередь может расти и сокращаться. Доступ обеспечивается двумя указателями: указателем начала, всегда указывающим на текущее начало очереди, и указателем конца, всегда указывающим на позицию, следующую за текущим концом очереди (пустое место, куда будет помещен новый элемент). Очередь растет циклически внутри зарезервированного блока; когда указатель конца очереди достигает конца блока, он перебрасывается на начало блока. Как этого избежать, почитайте Любимского, с. 135- 136-137.*

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

* Имеется в виду учебник МГУ (―Кирпич‖): Любимский Э.З., Мартынюк В.В., Трифонов Н.П. Программирование. М.: Наука, 1980, 608 с. (60 тыс. экз.).

144

указатель конца догоняет указатель начала. Это представление иллюстрируется рисунком. (рис. 3.14, с. 89)

Рис. 3.11. Представление очереди в памяти

Связанное представление очереди аналогично стекам, добавляется лишь указатель конца для облегчения включения элементов в конец очереди (см. рис. 3.15, с. 90).

3.5.3. Списки. Линейный массив переменного размера, в котором включения и исключения элементов могут осуществляться в произвольных точках, называется списком. Список состоит из элементов, называемых звеньями, которые имеют сложное строение. Звено состоит из двух частей: справки и тела звена (записи).

145

- с двумя связями, двунаправленные списки.

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

Головка не имеет записи, а содержит справку из трех элементов: длина звена N0 = 3; ссылка на начало первого звена, тело звена, заполненного ссылкой на начало свободного места зарезервированной памяти. В текущем (Ni-ом) звене в теле помещается запись. В указателе конечного звена записан 0 или (N) (если список циклический, то записывается указатель на головку списка).

Такой список имеет тот недостаток, что позволяет просматривать его только в одном направлении, и при этом "нельзя повернуть назад". Для того, чтобы обеспечить "реверс" в однонаправленном списке соединяют конец с началом, то есть делают его циклическим.

Хотя связанное распределение требует дополнительного пространства памяти (для размещения указателей), однако часто бывает, что в узлах (звеньях) имеется свободное пространство, в котором указатели можно разместить. (Тут требуется хорошее знание реализации списка в ЭВМ!)

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

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

147

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

3.5.3.2. Двунаправленный список. Это список, в котором каждый элемент связан как с последующим, так и с предыдущим элементом списка. В головке списка имеются указатели на первый и на последний элементы списка (рис. 3.16, с. 91).

Рис. 3.12. Представление списка с двумя связями

Заглавное звено этого списка имеет 4 значения: длина звена - 4; ссылка на первое звено (в начале = "4"); пустая ссылка (0) на предыдущее звено; указатель первого свободного элемента. Каждое промежуточное звено включает справку из 3х значений: длина звена; ссылка на следующее звено; ссылка на предыдущее звено; содержание записи в узле списка. В последнем звене (не кольцевого списка) ссылка на последнее звено равна 0.

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

148

Хотя двунаправленные списки занимают больше памяти, однако получающееся преимущество компенсирует эту потерю. Одно из дополнительных преимуществ (кроме "реверса") - возможность удаления узла с указанием только его адреса без указания предыдущего. Это очень важно при освобождении от случайных узлов, для которых нельзя реализовать доступ ни по индексу, практикуемому в последовательных структурах, ни по относительной позиции, практикуемому в списках.

3.5.3.3. Списки свойств. В стеках, очередях и списках невозможен доступ по индексам. Однако доступ с помощью индексов, являющихся произвольными идентификаторами, позволяет получить очень важный класс структур, напоминающих структуры неоднородных массивов (записей) с мнемоническими (уникальными) индексами (именами). Для этого необходимо, чтобы при каждом включении элемента фиксировалась бы и спецификация индекса, с помощью которого будет осуществляться доступ к элементу. Получающаяся в результате структура имеет множество пар "индекс - значение". Обычной упорядоченности в такой структуре не требуется, поскольку все операции доступа выполняются по заданным индексам. Линейные списки такого рода существуют во многих языках и называются по-разному (таблицами, списками описаний, списками атрибутов, значений). Будем их называть списками свойств, которые имеют широкое применение.

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

дуются) (см. рис. 3.17, с. 92).

149

Список свойств

Фамилия

Иванов

Возраст

…

Служащий

- 0 -

Рис. 3.13. Связанное представление списка свойств

3.5.4. Многомерные массивы переменного размера.

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

1.На линейный массив (список) типа дерева может быть только один указатель, хранящийся в другом массиве (то есть возникает "размножение") и не допускается циклическое связывание. Тогда каждый вновь созданный список становится подсписком только одного списка.

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

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

150