Лабораторная работа № 16

Работа со стеками и очередями.

Варианты заданий.

Как упоминалось ранее, для работы с очередью нужны следующие операции:

· создать пустую очередь (очистить очередь);

· проверить, является ли очередь пустой;

· добавить в конец очереди элемент;

· удалить из очереди первый элемент.

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

Представление очереди (n - целая константа больше 1):

1) для каждой очереди отводится свой массив из n компонентов некоторого типа, в котором элементы очереди занимают группу соседних компонентов, индексы первой и последней из которых запоминаются: при этом, когда очередь достигает правого края массива, все элементы сдвигаются к левому краю (рис 4,а);

2) аналогичное представление. но массив как бы склеивается в кольцо, поэтому, если очередь достигает правого края массива, то новые элементы записываются в начало массива (рис 4, б);

3) для каждой очереди создается сво однонаправленный список из элементов некоторого типа, при этом запоминаются ссылки на первое и последнее звенья списка (рис 4,в).

Н

К

...

Э1

Э2

...

Эm

1 2 Н-1 Н Н+1 К К+1 n

Рис. 4, а

Н

К

Эi+1

...

Эm

...

Э1

Э2

...

Эi

1 К К+1 Н-1 Н Н+1 n

Рис. 4, б

Э1 Э2... Эm nil

Рис. 4, в

2. Используя очередь (считать уже описанным тип очередь при подходящем типе и всех описанных ранее операций для работы с очередью) решить следующую задачу (решение записать в виде процедуры):

4) Type FR=file of real;

За один просмотр файла f типа FR и без использования дополнительных файлов напечатать элементы файла f в следующем порядке: сначала все числа меньше а, затем все числа из отрезка [a,b], и наконец все остальные числа, сохраняя исходный взаимный порядок в каждой из этих трех групп чисел (a и b заданные числа, a<b).

5) содержимое текстового файла f, разделенное на строки, переписать в текстовый файл g, перенося при этом в конец каждой строки все входящие в нее цифры (с сохранением исходного взаимного порядка как среди цифр, так и среди остальных литер строки).

6) type имя=(Анна,..., Яков);

дети=array[имя,имя]of boolean;

потомки=file of имя;

Считая заданным имя И и массив Д типа дети (Д[x,y]=true, если человек по имени y является ребенком человека по имени х), записать в файл П типа потомки имена всех потомков человека с именем И в следующем порядке:

- сначала имена всех его детей;

- всех его внуков;

- всех правнуков и т. д.

Как было сказано ранее, для работы со стеком обычно нужны следующие операции:

· создать пустой стек (очистить стек);

· проверить является ли стек пустым;

· добавить в конец стека элемент;

· удалить из стека последний элемент.

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

Представление стека (n - целая константа больше 1):

7) для стека отводится свой массив из n компонентов некоторого типа, в начале которого располагаются элементы стека, при этом запоминается индекс компонента массива, занятый последним элементом стека.

8) для каждого стека создается свой однонаправленный список, в котором элементы стека располагаются в обратном порядке.

4. Используя стек (считать уже описанным тип стек с элементами типа char, функцию проверки пустоты стека, процедуры создания, добавления и удаления) решить следующую задачу (решение записать в виде процедуры или функции).

9) напечатать содержимое текстового файла t, выписывая литеры каждой его строки в обратном порядке.

10) проверить, является ли содержимое текстового файла t правильной записью формулы следующего вида:

<формула>::=<терм>|<терм>+<формула>|

<терм>-<формула>

<терм>::=<имя>|(<формула>)|[<формула>]

<имя>::=x|y|z

11) в текстовом файле f записана без ошибок формула следующего вида:

<формула>::=<цифра>|М<формула>,<формула>|

m<формула>,<формула>

<цифра>::=0|1|2|3|4|5|6|7|8|9,

где М обозначает функцию max, m - min.

Вычислить (как целое число) значение данной формулы (например, М(5,m(6,8))=6).

12) в текстовом файле записано без ошибок логическое выражение (ЛВ) в следующем виде:

<ЛВ>::=true| false |(\<ЛВ>)| (<ЛВ>^<ЛВ>)| (<ЛВ>V<ЛВ>),

где знаки \, ^, V обозначают соответственно отрицание, конъюнкцию, дизъюнкцию.

Вычислить (как boolean) значение этого выражения.

5. Используя очередь и/или стек (считать уже описанными их типы и операции над ними) решение описать в виде процедуры).

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

<текст>::=<пусто>|<элемент><текст>

<элемент>::=<буква>|<текст>

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

13)закрывающих скобок;

14)открывающих скобок.

Например, для текста A+(45-F(X)*(B+C)) надо напечатать:

13) 8 10; 12 16; 3 17;

14) 3 17; 8 10; 12 16;

Под <выражением> будем понимать конструкцию следующего вида

<выражение>::=<терм>|<терм><знак+-><выражение>

<знак+->::=+|-

<терм>::=<множитель>|<множитель>*<терм>

<множитель>::=<число>|<переменная>|(<выражение>)|

<множитель>^<число>

<число>::=<цифра>

<переменная>::=<буква>,

где знак ^ обозначает возведение в степень.

Постфиксной формой записи выражения a^b называется запись, в которой знак операции размещен за операндами: ab^.

Например:

a+b-c это ab+c-

a*b+c это ab*c+

15) описать функцию value(postfix), которая вычисляет как целое число значение выражения (без переменных), записанного в постфиксной форме в текстовом файле postfix.

Использовать следующий алгоритм вычисления:

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

16) описать процедуру translate (infix, postfix), которая переводит выражение, записанное в обычной (инфиксной) форме в текстовом файле infix в постфиксную форму и в таком виде записывает его в текстовый файл postfix. Если встречается операнд (число или переменная), то он сразу переносится в файл postfix. Если встречается открывающая скобка, то она заносится в стек, а если встречается закрывающая скобка, то из стека извлекаются находящиеся там знаки операций до ближайшей открывающей скобки, которая тоже удаляется из стека, и все эти знаки в (порядке извлечения) записываются в файл postfix. Когда же встречается знак операции, то из конца стека извлекаются (до ближайшей скобки, которая сохраняется в стеке) знаки операций, старшинство которых больше или равно старшинству данной операции, и они записываются в файл postfix, после чего рассматриваемый знак заносится в стек. В заключение выполняются такие же действия, как если бы встретилась закрывающая скобка.

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

18) описать (нерекурсивную) процедуру postfixprint(infix), которая печатает в постфиксной форме выражение, записанное в инфиксной форме в текстовом файле infix.

Для решения следующих задач использовать двоичные деревья при следующем их описании:

type тип= некоторый тип элементов дерева;

дерево=^вершина;

вершина=record элем: тип элементов дерева;

лев, прав: дерево end;

В задачах Т, Т1, Т2 обозначают деревья, Е - величину некоторого типа элементов дерева.

6. Используя очередь или стек (считать уже описанными их типы и операции над ними) описать процедуру или функцию, которая:

1) присваивает параметру Е элемент из самого левого листа непустого дерева Т;

2) определяет число вхождений элемента Е в дерево Т;

3) вычисляет среднее арифметическое всех элементов непустого дерева Т (тип элементов дерева real);

4) заменяет в дереве Т все отрицательные элементы на их абсолютные значения (тип элементов дерева real);

5) меняет местами максимальный и минимальный элементы непустого дерева Т, все элементы которого различны (тип элементов дерева real);

6)печатает все элементы из всех листьев дерева Т (тип элементов дерева char);

7) печатает все элементы дерева Т по уровням: сначала - из корня дерева, затем (слева направо) - из вершин дочерних по отношению к корню, затем (слева направо) - из вершин дочерних по отношению к этим вершинам и т. д. (тип элементов дерева integer);

8) находит в непустом дереве Т длину пути от корня до ближайшей вершины с элементом Е, если Е не входит в Т, то за ответ принять -1.

9) подсчитывает число вершин на n-ом уровне непустого дерева Т (корень считать вершиной нулевого уровня).

7. Написать рекурсивную функцию или процедуру, которая:

10) определяет, входит ли элемент Е в дерево Т;

11) определяет число вхождений элемента Е в дерево Т;

12) вычисляет сумму всех элементов непустого дерева Т (тип элементов дерева real);

13) находит величину наибольшего элемента непустого дерева Т (тип элементов дерева real);

14)печатает все элементы из всех листьев дерева Т (тип элементов дерева char);

15) определяет максимальную глубину непустого дерева Т, т. е. число ветвей в самом длинном из путей от корня дерева до листьев;

16) подсчитывает число вершин на n-ом уровне непустого дерева Т (корень считать вершиной нулевого уровня);

17) Рекурсивно и нерекурсивно описать логическую функцию equal(T1, T2), проверяющую на равенство деревья Т1 и Т2;

18) описать процедуру copy(T, T1), которая строит дерево Т1 - копию дерева Т;

19) описать логическую функцию same (T), которая определяет, есть ли в дереве Т хотя бы два одинаковых элемента;

Опишем следующий вид дерева, который можно назвать “деревом-формулой”. Формулу вида:

<формула>::=<терминал>|<формула><знак><формула>

<знак>::=+|-|*

<терминал>::=0|1|2|3|4|5|6|7|8|9

можно представить в виде двоичного дерева с типом элементов дерева = char согласно следующим правилам: формула из одного терминала (цифры) представляется деревом из одной вершины с этим терминалом, а формула вида (f₁ s f₂) - деревом, в котором корень это знак s, а левое и правое поддеревья - это соответствующие представления формул f₁ и f_2. На рис. 5 показано дерево-формула, соответствующее формуле(5*(3+8))).

Рис. 5

Описать рекурсивную функцию или процедуру, которая:

20) вычисляет (как целое число) значение дерева-формулы Т;

21) по формуле из текстового файла F строит соответствующее дерево- формулу Т;

22) печатает дерево- формулу Т в виде соответствующей формулы;

23) проверяет, является ли двоичное дерево Т деревом формулой.