Файл: 2. Лекции Паскаль (Часть 2).doc

Добавлен: 19.10.2018

Просмотров: 4360

Скачиваний: 8

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

Оглавление

9. Файловые типы данных

9.1. Инициализация файла

9.2. Файлы и работа с ними

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

Работа с внешними файлами

Лабораторная работа №11, вариант № 5.

Работа с внешними файлами

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

9.3. Сортировка файлов.

9.3.1. Слияние упорядоченных последовательностей.

9.3.2. Сортировка сбалансированным слиянием

9.3.3. Сортировка простым слиянием

9.3.4. Сортировка естественным слиянием.

9.3.5. Сортировка многофазным слиянием.

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

Сортировка файлов.

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

Сортировка файлов.

10. Динамическая память.

10.1. Указатели.

10.2. Списки.

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

Исключение элементов списка.

Образец выполнения работы.

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

Исключение элементов списка.

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

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

Работа со списками.

Образец выполнения работы.

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

Работа со списками.

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

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

Выполнение операций над списковыми структурами.

Образец выполнения работы.

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

Выполнение операций над списковыми структурами.

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

10.3. Деревья.

10.4. Стеки, очереди.

Образец выполнения работы.

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

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

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

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

11. Организация меню с использованием средств среды Turbo Pascal

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

Составления меню.

Образец выполнения работы.

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

Составления меню.

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

Создание стека:

Исходное состояние

Т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, выписывая литеры каждой его строки в обратном порядке.