ВУЗ: Пермский национальный исследовательский политехнический университет
Категория: Лекция
Дисциплина: Программирование
Добавлен: 19.10.2018
Просмотров: 5241
Скачиваний: 10
СОДЕРЖАНИЕ
Лабораторная работа №11, вариант № 5.
9.3.1. Слияние упорядоченных последовательностей.
9.3.2. Сортировка сбалансированным слиянием
9.3.3. Сортировка простым слиянием
9.3.4. Сортировка естественным слиянием.
9.3.5. Сортировка многофазным слиянием.
Выполнение операций над списковыми структурами.
Выполнение операций над списковыми структурами.
Работа со стеками и очередями.
Работа со стеками и очередями.
11. Организация меню с использованием средств среды Turbo Pascal
Для работы со стеками необходимо иметь один основной указатель на вершину стека (Тор) и один дополнительный временный указатель (Р), который используется для выделения и освобождения памяти элементов стека.
Создание стека:
Исходное состояние
Тon : = nil
2. Выделение памяти под первый элемент стека и внесение в него информации
New (P)
P^. Inf : = S
P^. Link: = nil
Установка вершины стека Тор на созданый элемент
Тор: = Р
Добавление элемента стека:
1. Выделение памяти под новый элемент
New (P)
2. Внесение значения в информационное поле нового элемента и установка связи между ним и старой вершиной стека Тор
P^. Inf: = Val (Val=10)
P^. Link: = Top.
Помещение вершины стека Тор на новый элемент
Тор: = Р
Удаление элемента стека
Извлечение информации из информационного поля вершины стека Тор в переменную Val и установка на вершину стека вспомогательного указателя Р.
Val: = Top^. Inf;
P: = Top;
Перемещение указателя вершины стека Тор на следующий элемент и освобождение памяти, занимаемой «старой» вершиной стека
Тор: - Р^. Lin K;
Pispose (P)
В качестве примера приведем программу создания и удаления стека из десяти элементов:
Pvogram Stack;
Uses Crt
Tupe
TP tr = ^Telem;
Telem = record
Inf: Real;
Link: TPtr
End;
Var
Top: TPfr;
Value: Real;
Value: Byte;
Procedure Push (Val: Real)
Var
P: TPfr;
Begin
New (P);
P^.Inf: = Val;
P^.Link: = Top
Top: = P
End;
Procedure Top (Var Val:Real);
Var
P: TPtr;
Begin
Val: = Top^. Inf;
P: = Top;
Top: = P^. Link;
Pispose (P)
End;
Begin
ClrSer;
{начальные установки указателей}
Тор: = nil
{создание стека из десяти элементов}
for i: = 1 to 10 do Push (i);
{удаление стека с распечаткой значений его элементов}
whise Top <> nil do
begin
Pop (Value);
Writeln (‘Value= ‘ , Value = 5:2)
End;
End.
Очередь - это линейный список, в котором элементы включаются с одного конца, называемого хвостом, а выбираются и удаляются с другого конца, называемого вершиной. Дисциплина обслуживания очереди- “первым пришел - первым вышел” (FIFO - first in first out), т. е. первый включенный в очередь элемент первым из нее и удаляется.
Очередь – это частный случай линейного односвязующего списка для которого разрешены только два действия: добавление элемента в конец очереди и удаление элемента из начала очереди.
Для создания очереди и работы с ней необходимо иметь как минимум два указателя:
на начало очереди (возьмем идентификатор Beg Q)
на конец очереди (возьмем идентификатор End Q)
Кроме того, для освобождения памяти удаляемых элементов требуется дополнительный временный указатель (Р).
Создание очереди:
Исходное состояние:
Beg Q: = nil
Eng Q: = nil
Выделение памяти под первый элемент
New (P)
Занесение информации в первый элемент очереди
Beg Q: = P
Eng Q: = P
Добавление элемента очереди
Выделение памяти под новый элемент и занесение в него информации:
New (P)
P^, Inf: = 5
P^, Link: = hil
Установка связи между последним элементом очереди и новым, а также перемещение указателя конца очереди End Q на новый элемент
End^. Link: = P
End Q: = P
Удаление элемента очереди
Извлечение информации из удаляемого элемента в переменную Val и установка на него вспомогательного указателя Р
Val: = Beg Q^. Inf
P: = Beg Q
Перестановка указателя начала очередт Beg Q на следующий элемент используя значение поля Link, которое хранится в первом элементе. После этого освобождается память начального элемента очереди, используя дополнительный указатель P:
Beg Q: = P^. Link
Dispose (P)
В качестве примера приведем программу создания и удаления очереди из десяти элементов:
Prodrsm Queue;
Uses Crt;
Type
TPtr = ^Telem;
TFlem = record
Inf: Real;
Link: Tptr
End;
Var
Beg Q, End Q : TP tr;
Value : Real;
i : Byte;
Procedure AddEl (Val:Real)
{создает первый и дабавляет очередной элемент в конец очереди}
Var
P: TPtr
Begin
New (P);
P^. Inf: = Val;
P^. Link: = nil;
If End Q = n:l ; {если создается первый элемент очереди}
Then Beg Q: = P {если создается очередной элемент очереди}
Else Eng Q^. Link: = P;
End Q: = P;
End;
Procedure bet Del E1 (vav Val: Real)
{извлечение информации из начального элемента очереди с последующим освобождением его памяти}
Var
P: TPtr;
Begin
Val: = Reg Q^. Inf;
P: = Beg Q;
Beg Q: = P^. Link
If Beg Q = nil {если удаляется последний элемент очереди}
Then Eng Q: = nil;
Dispose (P);
End;
Begin
ClrScr;
{начальные установки указателей}
Beg Q: = nil;
Eng Q: = nil;
{создание очереди из 10 элементов}
for I: = 1 to 10 to Add E1 (i)
{удаление очереди с распечаткой значений её элементов}
while. Beg Q <> nil do
begin
Get Del E1 (Value);
Writeln (‘Value=’ , Value : 5: 2)
End;
End.
Образец выполнения работы.
Лабораторная работа № 16.
Работа со стеками и очередями.
Часть 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.
Результат работы программы:
Результат обхода дерева: длина пути к элементу со значением "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^.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.
Результат работы программы:
Максимальная глубина заданного дерева 7 узла(ов) Всего дерево содержит 37 узла(ов)
Press any key... |
Лабораторная работа № 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, выписывая литеры каждой его строки в обратном порядке.