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

Часть 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