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

Часть I

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

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

Текст программы:

Program T854a;

Uses CRT;

Const

E='C';

Type

Tree=^Root;

Root=Record

Element: Char;

Left, Right: Tree;

End;

Stack=^Description;

Description=Record

BTree: Tree;

Process: boolean;

Next: Stack;

End;

Var

T: Tree;

S: Stack;

{создает поддерево с двумя листьями}

Procedure SubTreeBuilding(var P: Tree);

Var

TLeft, TRight: Tree;

Begin

New(P);

New(TLeft);

New(TRight);

TLeft^.Left: =nil;

TLeft^.Right: =nil;

TRight^.Left: =nil;

TRight^.Right: =nil;

TLeft^.Element: =Chr(64+Random(28));

TRight^.Element: =Chr(64+Random(28));

P^.Element: =Chr(64+Random(28));

P^.Left: =TLeft;

P^.Right: =TRight;

End;

{создает дерево}

Procedure TreeBuild;

Begin

Randomize;

SubTreeBuilding(T);

SubTreeBuilding(T^.Left);

SubTreeBuilding(T^.Right);

SubTreeBuilding(T^.Left^.Left);

SubTreeBuilding(T^.Right^.Left);

SubTreeBuilding(T^.Left^.Right);

SubTreeBuilding(T^.Right^.Right);

SubTreeBuilding(T^.Left^.Left^.Left);

SubTreeBuilding(T^.Right^.Left^.Left);

SubTreeBuilding(T^.Left^.Right^.Left);

SubTreeBuilding(T^.Right^.Right^.Left);

SubTreeBuilding(T^.Left^.Left^.Right);

SubTreeBuilding(T^.Right^.Left^.Right);

SubTreeBuilding(T^.Left^.Right^.Right);

SubTreeBuilding(T^.Right^.Right^.Right);

SubTreeBuilding(T^.Left^.Left^.Right^.Right);

SubTreeBuilding(T^.Right^.Left^.Right^.Right);

{T^.Right^.Left^.Right^.Right^.Right^.Element: ='E'; }

End;

{************* Функции и процедуры работы со стеком *****************}

{** Процедура создания и очистки стека **}

Procedure InitStack(var S1: Stack);

var

P1, P2: Stack;

Begin

While S1< > nil Do Begin

P1: =S1^.Next;

Dispose(S1);

S1: =P1;

End;

{** Процедура проталкивания элемента в стек **}

Procedure Shoot(E: Tree);

var

P: Stack;

Begin

New(P);

P^.BTree: =E;

P^.Process: =false;

P^.Next: =S;

S: =P

End;

{ **Функция выталкивания элементов из стека **}

Procedure Pull(var S1: Stack);

var

P: Stack;

Begin

If S1< > nil Then Begin

P: =S1;

S1: =S1^.Next;

Dispose(P);

P: =nil;

End

Else

S1: =nil;

End;

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

Function Detect_Stack_Size(S1: Stack): Integer;

var

i: Integer;

Begin

i: =0;

While S1< > nil Do begin

inc(i);

S1: =S1^.Next;

End;

Detect_Stack_Size: =i;

End;

{находит длину пути от корня до ближайшей вершины с элементом Е}

Procedure Count_Waypoints(T1: Tree);

var

i: Integer;

P: Tree;

Begin

InitStack(S);

Shoot(T1); {проталкиваем в стек корень дерева}

i: =0;

{****** Цикл обхода дерева ********}

Repeat

inc(i);

P: =S^.Btree; {P-узел на верхушке стека}

{** Если текущий элемент стека - лист **}

If ((P^.Left=nil) and (P^.Right=nil) and (Detect_Stack_Size(S)> 0)) Then Begin

Pull(S);

S^.Process: =true;

{Если данный лист - не правый сын своего отца}

If P< > S^.BTree^.Right Then Begin

S^.Process: =true;

Shoot(S^.BTree^.Right); {проталкиваем в стек его правого брата}

End

Else Begin {** элемент на верхушке стека-промежуточный узел **}

If (not S^.Process) Then Begin {данное дерево еще не обработано}

S^.Process: =false;

Shoot(P^.Left); {протолкнуть в стек левого сына}

End

Else Begin {данное дерево уже обработано}

Pull(S);

If ((Detect_Stack_Size(S)> 0) And (P< > S^.Btree^.Right)) {элемент-не корень}

Then Begin {и не правый сын своего отца}

S^.Process: =true;

Shoot(S^.Btree^.Right); {проталкиваем правого брата}

End;

Until ((Detect_Stack_Size(S)=0) or (S^.Btree^.Element=E));

If ((Detect_Stack_Size(S)=0) And (S^.Btree^.Element< > E)) Then

WriteLn('Указанное значение " ', E, '" в дереве не найдено, результат равен " 1" ')

Else

WriteLn('длина пути к элементу со значением " ', E, '" - ', Detect_Stack_Size(S)-1, ' узла(ов)');

WriteLn('Всего произведено ', i, ' перемещений по узлам дерева');

End;

Begin

TreeBuild;

WriteLn;

WriteLn('Результат обхода дерева: ');

Count_Waypoints(T);

WriteLn;

WriteLn('Press any key...');

Repeat Until Keypressed;

End.

Результат работы программы:

Результат обхода дерева: длина пути к элементу со значением " C" - 2 узла(ов) Всего произведено 15 перемещений по узлам дерева Press any key...

Часть II

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

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

Текст программы T854b:

Program Task854b;

Uses CRT;

Type

Tree=^Root;

Root=Record

Element: Char;

Left, Right: Tree;

End;

Var

T: Tree;

Depth, n: Integer;

{создает поддерево с двумя листьями}

Procedure SubTreeBuilding(var P: Tree);

Var

TLeft, TRight: Tree;

Begin

New(P);

New(TLeft);

New(TRight);

P^.Element: =Chr(64+Random(28));

TLeft^.Left: =nil;

TLeft^.Right: =nil;

TRight^.Left: =nil;

TRight^.Right: =nil;

TLeft^.Element: =Chr(64+Random(28));

TRight^.Element: =Chr(64+Random(28));

P^.Left: =TLeft;

P^.Right: =TRight;

End;

Procedure Tree_Build;

Begin

Randomize;

SubTreeBuilding(T);

SubTreeBuilding(T^.Left);

SubTreeBuilding(T^.Right);

SubTreeBuilding(T^.Left^.Left);

SubTreeBuilding(T^.Right^.Left);

SubTreeBuilding(T^.Left^.Right);

SubTreeBuilding(T^.Right^.Right);

SubTreeBuilding(T^.Right^.Left^.Left);

SubTreeBuilding(T^.Left^.Right^.Left);

SubTreeBuilding(T^.Right^.Right^.Left);

SubTreeBuilding(T^.Left^.Left^.Right);

SubTreeBuilding(T^.Right^.Left^.Right);

SubTreeBuilding(T^.Left^.Right^.Right);

SubTreeBuilding(T^.Right^.Right^.Right);

SubTreeBuilding(T^.Left^.Left^.Right^.Right);

SubTreeBuilding(T^.Right^.Left^.Right^.Right);

SubTreeBuilding(T^.Right^.Left^.Right^.Right^.Left);

SubTreeBuilding(T^.Right^.Left^.Right^.Right^.Left^.Right);

End;

procedure Detect_Tree_Depth(r: tree; Layer: Integer);

begin

if r< > nil then

begin

Detect_Tree_Depth(r^.left, Layer+1);

If Layer> Depth Then Depth: =Layer;

Detect_Tree_Depth(r^.right, Layer+1);

If Layer> Depth Then Depth: =Layer;

inc(n);

end;

Begin

Tree_Build;

Depth: =0;

n: =0;

Detect_Tree_Depth(T, 0);

WriteLn;

WriteLn('Максимальная глубина заданного дерева ', Depth, ' узла(ов)');

WriteLn('Всего дерево содержит ', n, ' узла(ов)');

WriteLn;

WriteLn('Press any key...');

Repeat until Keypressed;

End.

Результат работы программы:

Максимальная глубина заданного дерева 7 узла(ов) Всего дерево содержит 37 узла(ов) Press any key...

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

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

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

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

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

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

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

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

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

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

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

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

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

...

Э₁

Э₂

...

Э_m

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

Рис. 4, а

Э_i+1

...

Э_m

...

Э₁

Э₂

...

Э_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) проверяет, является ли двоичное дерево Т деревом формулой.

⇐ Предыдущая 8 9 10 11 12 13 14 15 1617