![]() |
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Работа со стеками и очередями.⇐ ПредыдущаяСтр 17 из 17
Часть 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; 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 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; End; 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.
Результат работы программы:
Часть 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^.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; 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. Результат работы программы:
Лабораторная работа № 16. Работа со стеками и очередями. Варианты заданий.
Как упоминалось ранее, для работы с очередью нужны следующие операции: · создать пустую очередь ( очистить очередь); · проверить, является ли очередь пустой; · добавить в конец очереди элемент; · удалить из очереди первый элемент. 1. Необходимо для каждого из указанных ниже представлений очереди описать соответствующий тип очередь, считая, что все элементы очереди имеют некоторый тип, и реализовать в виде процедур и функций перечисленные операции над очередью. Представление очереди (n - целая константа больше 1): 1) для каждой очереди отводится свой массив из n компонентов некоторого типа, в котором элементы очереди занимают группу соседних компонентов, индексы первой и последней из которых запоминаются: при этом, когда очередь достигает правого края массива, все элементы сдвигаются к левому краю (рис 4,а); 2) аналогичное представление. но массив как бы склеивается в кольцо, поэтому, если очередь достигает правого края массива, то новые элементы записываются в начало массива (рис 4, б);
3) для каждой очереди создается сво однонаправленный список из элементов некоторого типа, при этом запоминаются ссылки на первое и последнее звенья списка (рис 4,в).
1 2 Н-1 Н Н+1 К К+1 n Рис. 4, а
1 К К+1 Н-1 Н Н+1 n
Рис. 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 согласно следующим правилам: формула из одного терминала (цифры) представляется деревом из одной вершины с этим терминалом, а формула вида (f1 s f2 ) - деревом, в котором корень это знак s, а левое и правое поддеревья - это соответствующие представления формул f1 и f2. На рис. 5 показано дерево-формула, соответствующее формуле(5*(3+8))).
Рис. 5 Описать рекурсивную функцию или процедуру, которая: 20) вычисляет (как целое число ) значение дерева-формулы Т; 21) по формуле из текстового файла F строит соответствующее дерево- формулу Т; 22) печатает дерево- формулу Т в виде соответствующей формулы; 23) проверяет, является ли двоичное дерево Т деревом формулой.
Читайте также:
![]() |
Последнее изменение этой страницы: 2016-03-15; Просмотров: 1330; Нарушение авторского права страницы