скачать rtf
2. СТЕКИ И ОЧЕРЕДИ
2.1. Спецификация стека и очереди
Ранее в 1.2 и 1.5 при задании спецификации линейных списков использовалась абстракция (модель) последовательности. При этом были определены функции над последовательностями First, Last, Rest, Lead, Prefix и Postfix. Напомним эти определения, сохранив те же обозначения, что и ранее, и дополнительно обозначив тип последовательности w = [ x1, x2, ..., xn] из элементов xi типа El как Sequence (El). Функции First, Last, Rest, Lead определены только для непустых последовательностей (w ∆):
First: Sequence (El) El; First (w) = x1;
Last: Sequence (El) El; Last (w) = xn;
Rest: Sequence (El) Sequence (El); Rest (w) = [ x2, ..., xn ];
Lead: Sequence (El) Sequence (El); Lead (w) = [ x1, x2, ...,xn1].
Функции Prefix и Postfix определены для любых последовательностей:
Prefix: El Sequence (El) Sequence (El);
Postfix: Sequence (El) El Sequence (El);
Prefix (x0, w) = [ x0, x1, x2, ..., xn ]; Postfix (w, x) = [ x1, x2, ..., xn, x ].
Таким образом, набор функций First, Rest, Prefix, Last, Lead, Postfix обеспечивает доступ к элементам последовательности («чтение» элементов из последовательности и дописывание элементов в последовательность) только через ее начало и ее конец. Последовательность может рассматриваться как самостоятельная структура данных. Тогда функции First, Rest, Last, Lead селекторы, а функции Prefix и Postfix конструкторы типа Sequence (El). Более того, используя разные подмножества набора базовых функций этой структуры, получают различные полезные структуры данных. Так, если ограничиться только функциями First, Rest, Prefix (или только функциями Last, Lead, Postfix), то получается структура данных, известная как стек (или магазин). Рассмотрение только функций First, Rest, Postfix (или только Last, Lead, Prefix) соответствует структуре данных очередь (англ. queue). Если же используют весь набор функций, то соответствующую структуру данных обычно называют дек (от англ. deq аббревиатуры сочетания double-ended-queue, т. е. «очередь с двумя концами»). Во все эти структуры данных необходимо добавить еще две функции: 1) предикат-индикатор Null: Sequence (El) Boolean, идентифицирующий пустую последовательность ∆, и 2) либо константу, обозначающую пустую последовательность, либо функцию, порождающую значение ∆, например Create: Sequence (El).
Рассмотрим формальную спецификацию стека из элементов типа α (Stack of α Stack (α)). При этом для обозначения функций First, Rest, Prefix будем использовать исторически сложившиеся синонимы Top, Pop и Push соответственно (Top верхушка стека, Pop {up} вытолкнуть (вверх), Push {down} – втолкнуть, вжать (вниз)). Функциональная спецификация стека задается следующими определениями (множество непустых стеков обозначим как Non_null_stack):
1) Create: Stack (α);
2) Null: Stack (α) Boolean;
3) Top: Non_null_stack (α) α;
4) Pop: Non_null_stack (α) Stack (α);
5) Push: α Stack (α) Stack (α)
и набором аксиом (p: α; s: Stack (α); t: Non_null_stack (α)):
A1) Null (Create) = true;
A2) Null (Push (p, s)) = false;
A3) Top (Push (p, s)) = p;
A4) Pop (Push (p, s)) = s;
A5) Push (Top (s), Pop (s)) = s.
Можно заметить, что так определенный абстрактный тип Stack (α) фактически (с точностью до обозначений и несущественных деталей) совпадает с рассмотренным в 1.6 типом L_list (α).
Часто при определении стека вместо функции Pop используют функцию (процедуру), совмещающую результат действия функций Top и Pop. Обозначим такую процедуру Pop2. Тогда
Pop2: Non_null_stack (α) α Stack (α).
Можно явно определить Pop2 через функции Top и Pop:
| procedure Pop2 (out p: α; in-out s: Stack (α)); |
| begin |
| p := Top (s); s := Pop (s) |
| end |
Функциональная спецификация очереди из элементов типа α (Queue of α Queue (α)) задается следующими определениями:
1) Create: Queue (α);
2) Null: Queue (α) Boolean;
3) First: Non_null_queue (α) α;
4) Rest: Non_null_queue (α) Queue (α);
5) Postfix: Queue (α) α Queue (α)
и набором аксиом (p: α; q: Queue (α)):
A1) Null (Create) = true;
A2) Null (Postfix (q, p)) = false;
A3) First (Postfix (q, p)) = if Null (q) then p else First (q);
A4) Rest (Postfix (q, p)) = if Null (q) then Create
else Postfix (Rest (q), p).
В качестве примера использования базовых функций при операциях над очередью дадим определение функции сцепления двух очередей q1 и q2:
Concat (q1, q2) ≡ if Null (q1) then q2 else if Null (q2) then q1
else {not Null (q1) & not Null (q2)}
Concat (Postfix (q1, First (q2)), Rest (q2))
2.2. Реализация стека и очереди
Ссылочная реализация стека и очереди в динамической памяти в основном аналогична ссылочной реализации линейных списков, подробно рассмотренной в 1.3. Упрощение здесь связано с отсутствием необходимости работать с текущим («внутренним») элементом списка. Идеи такой реализации ясны из рис. 2.1.
Рис. 2.1. Ссылочное представление стека и очереди
Для ссылочной реализации дека естественно использовать Л2 список (см. 1.5).
Поскольку для стека, очереди и дека доступ к элементам осуществляется только через начало и конец последовательности, то эти структуры данных допускают эффективную непрерывную реализацию на базе вектора (в отличие от Л1- и Л2 списков, см. 1.1, с. 4).
При непрерывной реализации ограниченного стека на базе вектора для представления стека используется одномерный массив (вектор) Mem: array [1..n] of α и переменная Верх: 1..n (рис. 2.2).
Рис. 2.2. Непрерывное представление стека в векторе
Для пустого стека Верх = 0, для целиком заполненного стека Верх = n. Вершина стека доступна как Mem [Верх], операция Pop реализуется как Верх:= Верх 1, а операция Push (p, s) как begin Верх:= Верх + 1; Mem [Верх]: = p end при 0 ≤ Верх < n.
На базе одного вектора можно реализовать два стека, ограниченных в совокупности. Такую реализацию иллюстрирует рис. 2.3.
Рис. 2.3. Непрерывное представление двух стеков,
ограниченных в совокупности
Рассмотрим основные идеи непрерывной реализации ограниченной очереди на базе вектора. На рис. 2.4 изображен вектор Mem [1..n] и переменные Начало, Конец: 1..n, идентифицирующие начало и конец очереди при ее непрерывном размещении в векторе Mem.
Рис. 2.4. Непрерывное представление очереди в векторе
Особенностью такого представления является наличие ситуации, когда последовательность элементов очереди по мере их добавления может выходить за границу вектора, продолжаясь с его начала (вектор имитирует здесь так называемый кольцевой буфер). Эта ситуация изображена на рис. 2.5.
Рис. 2.5. Непрерывное представление очереди в кольцевом буфере
Двух переменных Начало и Конец недостаточно, чтобы различить в данном представлении, например, два следующих состояния очереди: 1) Начало = Конец + 1 и очередь пуста (рис. 2.6, а); 2) Начало = Конец + 1 и очередь полна (рис. 2.6, б). Простым решением этой проблемы является введение еще одной переменной, идентифицирующей состояние очереди, а именно переменной Длина, значение которой задает текущее количество
а
б
Рис.2.6. Два состояния очереди, при которых Начало=Конец+1:
а – очередь пуста, б – очередь полна
элементов в очереди (для пустой очереди Длина = 0, для полной очереди Длина = n).
Аналогичным образом может быть реализован дек.
2.3. Упражнения
В заданиях 1 – 3 следует использовать очередь и операции над ней; при этом очередь может быть реализована как на базе вектора, так и в связанной памяти (ссылочная реализация).
1. За один просмотр заданного файла F (типа file of Real) и без использования дополнительных файлов вывести элементы файла F в следующем порядке: сначала все числа, меньшие a, затем все числа на отрезке [a, b] и наконец все остальные числа, сохраняя исходный взаимный порядок в каждой из этих групп чисел (a и b задаются пользователем, a < b).
2. Содержимое заданного текстового файла F, разделенного на строки, переписать в текстовый файл G, перенося при этом в конец каждой строки все входящие в нее цифры (с сохранением исходного взаимного порядка как среди цифр, так и среди остальных литер строки).
3. Рассматриваются следующие типы данных:
type имя = (Анна, ..., Яков);
дети = array [имя, имя] of Boolean;
потомки = file of имя.
Задан массив Д типа дети (Д [x, y] = true, если человек по имени y является ребенком человека по имени x). Для введенного пользователем имени И записать в файл П типа потомки имена всех потомков человека с именем И в следующем порядке: сначала имена всех его детей, затем всех его внуков, затем всех правнуков и т. д.
В заданиях 4 – 8 следует использовать стек и операции над ним; при этом стек может быть реализован как на базе вектора, так и в связанной памяти (ссылочная реализация).
4. Содержимое заданного текстового файла F, разделенного на строки, переписать в текстовый файл G, выписывая литеры каждой строки в обратном порядке.
5. Правильная скобочная конструкция с тремя видами скобок определяется как
< текст > ::= < пусто > | < элемент > < текст >
< элемент > ::= < символ > | ( < текст > ) | [ < текст > ] | { < текст > }
где < символ > любой символ, кроме ( , ) , [ , ] , { , }. Проверить, является ли текст, содержащийся в заданном файле F, правильной скобочной конструкцией; если нет, то указать номер ошибочной позиции.
6. Проверить, является ли содержимое заданного текстового файла F правильной записью формулы следующего вида:
< формула > ::= < терм > | < терм > + < формула > | < терм > - < формула >
< терм > ::= < имя > | ( < формула > ) | [ < формула > ] | { < формула > }
< имя > ::= x | y | z
Если не является, то указать номер ошибочной позиции.
7. В заданном текстовом файле F записана формула вида
< формула > ::= < цифра > | М ( < формула > , < формула > ) |
m ( < формула > , < формула > )
< цифра > ::= 0 | 1 | ... | 9
где M обозначает функцию max, а m – функцию min. Вычислить (как целое число) значение данной формулы. Например, M (5, m(6, 8)) = 6.
8. В заданном текстовом файле F записано логическое выражение (ЛВ) в следующей форме:
<ЛВ>::= true | false | (< ЛВ > ) | ( < ЛВ > < ЛВ > ) | ( < ЛВ > < ЛВ > )
где знаки , и обозначают соответственно отрицание, конъюнкцию и дизъюнкцию. Вычислить (как Boolean) значение этого выражения.
В заданиях 9 – 11 следует использовать очередь и/или стек и операции над ними.
9. В заданном текстовом файле F записан текст, сбалансированный по круглым скобкам:
< текст > ::= < пусто > | < элемент > < текст >
< элемент > ::= < символ > | ( < текст > )
где < символ > – любой символ, кроме (, ). Для каждой пары соответствующих открывающей и закрывающей скобок вывести номера их позиций в тексте, упорядочив пары в порядке возрастания номеров позиций:
а) закрывающих скобок; б) открывающих скобок.
Например, для текста A + (45 F (X) * (B C)) надо напечатать:
а) 8 10; 12 16; 3 17; б) 3 17; 8 10; 12 16.
10. Определить, имеет ли заданная в файле F символьная строка следующую структуру:
a D b D c D d ...,
где каждая строка a, b, c, d, ..., в свою очередь, имеет вид x1 C x2. Здесь x1 есть строка, состоящая из символов A и B, а x2 строка, обратная строке x1 (т. е. если x1 = ABABB, то x2 = BBABA). Таким образом, исходная строка состоит только из символов A, B, C и D. Исходная строка может читаться только последовательно (посимвольно) слева направо.
11. Рассматривается выражение следующего вида:
< выражение >::= < терм > | < терм > + < выражение > |
< терм > < выражение >
< терм > ::= < множитель > | < множитель > * < терм >
< множитель > ::= < число > | < переменная > | ( < выражение > ) |
< множитель > ^ < число >
< число > ::= < цифра >
< переменная > ::= < буква >
Такая форма записи выражения называется инфиксной.
Постфиксной (префиксной) формой записи выражения aDb называется запись, в которой знак операции размещен за (перед) операндами: abD ( Dab ).
Примеры
Инфиксная Постфиксная Префиксная
ab ab ab
a*b+c ab*c+ +*abc
a*(b+c) abc+* *a+bc
a+b^c^d*e abc^d^e*+ +a*^b^cde.
Отметим, что постфиксная и префиксная формы записи выражений не содержат скобок.
Требуется:
а) вычислить как целое число значение выражения (без переменных), записанного в постфиксной форме в заданном текстовом файле postfix;
б) то же для выражения в префиксной форме (задан текстовый файл prefix);
в) перевести выражение, записанное в обычной (инфиксной) форме в заданном текстовом файле infix, в постфиксную форму и в таком виде записать его в текстовый файл postfix;
г) то же, но в префиксную форму (записать в файл prefix);
д) вывести в обычной (инфиксной) форме выражение, записанное в постфиксной форме в заданном текстовом файле postfix (рекурсивные процедуры не использовать и лишние скобки не выводить);
е) то же, но при заданной префиксной форме (в файле prefix).