ВУЗ: Пермский национальный исследовательский политехнический университет
Категория: Лекция
Дисциплина: Программирование
Добавлен: 19.10.2018
Просмотров: 5236
Скачиваний: 10
СОДЕРЖАНИЕ
Лабораторная работа №11, вариант № 5.
9.3.1. Слияние упорядоченных последовательностей.
9.3.2. Сортировка сбалансированным слиянием
9.3.3. Сортировка простым слиянием
9.3.4. Сортировка естественным слиянием.
9.3.5. Сортировка многофазным слиянием.
Выполнение операций над списковыми структурами.
Выполнение операций над списковыми структурами.
Работа со стеками и очередями.
Работа со стеками и очередями.
11. Организация меню с использованием средств среды Turbo Pascal
Способ построения линейного списка: начиная с пустого списка, последовательно добавлять элементы в его начало.
Процесс формирования списка из n элементов:
First: = nil; {начало с пустого списка}
While n>0 do begin
New (r); r^. Next: = first; r^. Number: = n;
First: = r; n: = n-1 end;
Основные операции со списками
Просмотр списка
Напишем процедуру, которая вывод на экран значение поля number элементов списка.
{просмотр списка}
procedure Print (first: point);
Var r: point
Begin
R: = first;
While r<>nil do begin
Writeln (‘number = ‘ , r^. Number);
R:= r^. Next; End;
Поиск в списке
Очень частая операция – поиск в списке элементов с заданным значением ключевого поля х. Так же как в случае файлов, поиск ведется последовательно. Он заканчивается либо когда элемент найден, либо когда достигнут конец списка.
{поиск в линейном списке}
Procedure Search (first: point; x: integer; var q: point);
{q – звращает указатель на найденный элемент; q – nil, если элемент с ключем х в списке нет}
var r: point;
ok: boolean;
begin
r: = first; ok: = true;
while (r<>nil) and ok do
if r^. Number = x then
ok: = false;
else r: = r^. Next; q: = r
end;
Включить элемент в список
Элемент нужно включить в середину списка после элемента, на который указывает ссылка q. Процедура включения записывается следующим образом.
{включить элемент в середину списка перед q^}
Procedure Insert (Var q: point; x: integer):
{х – значение информационного поля включаемого элемента}
Var r: point
Begin
New (r); {размещаем элемент в памяти}
R^. Number: = x;
{меняем ссылку}
r^/ next: = q^. Next; q^. Next: = r
end;
Если требуется включить перед элементом q^, а не после него, то кажется, что однонаправленная цепочка связей создает трудность, поскольку нет “прохода” к элементам, предшествующим данному. Однако эту проблему можно решить, используя простой прием, который состоит в том, что новый элемент вставляется после q^, но затем происходит обмен значениями между новым элементом и q^.
{включить элемент в середину списка перед q^}
Procedure insert Before (Var q: point; x: integer);
Var r: point;
Begin
New ( r ); {размещаем элемент памяти}
{включаем элемент после q^}
r^. Next: = q^. Next; q^. Next: = r;
{выполняем обмен значениями}
r^. Number: = q^. Nunber;
q^. Number: = x
end;
Удалить элемент из списка
Посмотрим как удаляется элемент из середины списка. Следует иметь в виду, что этот довольно очевидный и простой прием можно применять только в случае, когда y q^ есть последующий элемент, т.е он не является последним в списке.
Предположим, что надо удалить элемент, расположенный после элемента, на который указывает ссылка q
{удаление элемента из середины списка после q^}
Procedure Del (Var q: point);
Var r: point;
Begin
r: = q^. Next;
q^. Next: = q^. Next;
r^. Next: = nil
End;
Если следует удалить элемент на который указывается ссылка q, то следует в начале присвоить элементу q^ значение следующего за ним элемента, а затем этот элемент удалить.
{удаление элемента q^}
Prrocedure Deiet (Var q: point):
Var r: point;
Begin
r: = q^. next;
q^: = r^;
r^. Next: = nil; End;
Обратите внимание на то, что удаляемый из списка элемент остается в памяти и к нему имеется доступ к указателю r, так что в дальнейшем этот элемент можно вставить, например, в другой список. Если требуется освободить занимаемую этим элементом память, то следует выполнить
Dispose ( r );
r : = nil
Лабораторная работа № 13.
Исключение элементов списка.
Цель задания:
1. Ознакомиться с возможностью выполнения операции исключения элементов из списка.
2. Закрепление навыков использования переменных ссылочных типов данных.
Постановка задачи:
-
Составить список учебной группы, содержащей 20 учащихся.
-
Указать для каждого учащегося оценки, полученные на четырех экзаменах.
-
Разработать программу, которая вводит с экрана данные о каждом учащемся и заносит эти данные в однонаправленный список.
-
Обработать список согласно конкретному варианту.
Содержание отчета:
-
Постановка задачи.
-
Текст программы и результаты ее выполнения.
Образец выполнения работы.
Лабораторная работа № 13.
Исключение элементов списка.
Цель задания:
1. Ознакомиться с возможностью выполнения операции исключения элементов из списка.
2. Закрепление навыков использования переменных ссылочных типов данных.
Постановка задачи:
Составить список учебной группы, содержащей 20 учащихся.
Указать для каждого учащегося оценки, полученные на четырех экзаменах. Разработать программу, которая вводит с экрана данные о каждом учащемся и заносит эти данные в однонаправленный список.
Обработать список согласно конкретному варианту.
Содержание отчета:
1. Постановка задачи.
2. Текст программы и результаты ее выполнения.
Вариант задания:
Одна оценка 4, а остальные 3.
Текст программы:
{Исключение элементов из списка}
Program ExludingelementsFromList;
Uses CRT;
Type
PStudents= ^TStudents;
TStudents= Record
Name: String[20];
Marks: Array [1..4] of ShortInt;
Next:PStudents;
End;
Var
PS:PStudents; {указатель на последний элемент списка в статической памяти}
{ Процедура заполнения списка }
Procedure Init;
Var
i,y:Integer;
pro:PStudents;
Label
Exits;
Begin
PS^.Next:=nil; {последний элемент списка}
y:=1;
While true Do Begin
New(pro); {выделяем память под переменную с указателем pro}
{Присваиваем значение переменной}
WriteLn('Введите Ф.И.О. ',y,'-го студента, "Enter" - завершение программы');
ReadLn(pro^.Name);
If pro^.Name='' Then GoTo Exits;
WriteLn('Введите оценки студента (всего 4)');
For i:=1 To 4 Do ReadLn(pro^.Marks[i]);
pro^.Next:=PS; {записываем в поле Next указатель на предыдущий элемент}
PS:=pro; {указателю на голову списка присваиваем новое значение
т.е значение текущего элемента}
Inc(y);
End;
Exits : End;
{Процедура удаления элементов из списка }
Procedure Removing;
Var
Head,p1,p2:PStudents;
i,e3,e4:ShortInt;
Label
Exits;
Begin
head:=PS; {первый элемент-голова списка}
p2:=PS; {текущий указатель}
p1:=PS; {указатель на предыдущий элемент}
While True Do Begin
e4:=0; e3:=0;
For i:=1 to 4 Do Begin {подсчет оценок}
If p2^.Marks[i]=4 Then inc(e4);
If p2^.Marks[i]=3 Then inc(e3);
End;
If (e4=1) And (e3=3) Then {проверка условия на удаление}
If (Head=P2) Then Begin {если удаляемый элемент - голова списка}
PS:=PS^.Next; {новая голова}
Dispose(p2); p2:=PS; p1:=PS; Head:=PS;
End
Else Begin {если элемент в середине списка}
p1^.Next:=p2^.Next; {полю Next предыдущего элемента
присваиваем указатель следующего за текущим}
Dispose(p2); p2:=p1^.Next; {уничтожаем ссылку на текущий элемент}
End
Else Begin
p2:=p2^.Next;{если ничего не удалялось
передвигаем указатель на следующий элемент}
p1:=p1^.Next; {передвигаем указатель предыдущего элемента}
End;
If (p2=nil) Then GoTo Exits;
End;
Exits:End;
{Процедура вывода на печать списка }
Procedure PrintOut;
var
p1:PStudents;
Label
Exits;
Begin
p1:=PS;
While True Do Begin
WriteLn(p1^.Name);
If p1^.Next=nil Then GoTo Exits;
p1:=p1^.Next;
End;
Exits:End;
{Тело программы }
Begin
Init;
Removing;
PrintOut;
WriteLn('Нажмите любую клавишу...');
Repeat Until KeyPressed;
End.
Результат работы программы:
Введите Ф.И.О. 1-го студента, "Enter" - завершение программы Иванов И.И. Введите оценки студента (всего 4) 4 2 3 5 Введите Ф.И.О. 2-го студента, "Enter" - завершение программы Петров П.П. Введите оценки студента (всего 4) 5 5 5 5 Введите Ф.И.О. 3-го студента, "Enter" - завершение программы Сидоров С.С. Введите оценки студента (всего 4) 4 3 3 3 Введите Ф.И.О. 4-го студента, "Enter" - завершение программы Иваненко И.И. Введите оценки студента (всего 4) 4 3 3 3 Введите Ф.И.О. 5-го студента, "Enter" - завершение программы Петренко Введите оценки студента (всего 4) 5 3 2 1 Введите Ф.И.О. 6-го студента, "Enter" - завершение программы Сидоренко С.С. Введите оценки студента (всего 4) 3 4 3 3 Введите Ф.И.О. 7-го студента, "Enter" - завершение программы Иванчук И.И. Введите оценки студента (всего 4) 2 3 4 2 Введите Ф.И.О. 8-го студента, "Enter" - завершение программы Петрук П.П. Введите оценки студента (всего 4) 5 5 5 3 Введите Ф.И.О. 9-го студента, "Enter" - завершение программы Сидорчук С.С. Введите оценки студента (всего 4) 3 3 3 4 Введите Ф.И.О. 10-го студента, "Enter" - завершение программы Самосадкин С.С. Введите оценки студента (всего 4) 4 3 3 3 Введите Ф.И.О. 11-го студента, "Enter" - завершение программы Самоделкин С.С. Введите оценки студента (всего 4) 4 3 4 3 Введите Ф.И.О. 12-го студента, "Enter" - завершение программы Самопалкин С.С. Введите оценки студента (всего 4) 3 3 3 4 Введите Ф.И.О. 13-го студента, "Enter" - завершение программы Самохвалкин С.С. Введите оценки студента (всего 4) 3 4 3 3 Введите Ф.И.О. 14-го студента, "Enter" - завершение программы Самострелкин С.С. Введите оценки студента (всего 4) 2 3 3 3 Введите Ф.И.О. 15-го студента, "Enter" - завершение программы Самоедкин С.С. Введите оценки студента (всего 4) 4 3 3 3 Введите Ф.И.О. 16-го студента, "Enter" - завершение программы Самогонкин С.С. Введите оценки студента (всего 4) 3 3 4 3 Введите Ф.И.О. 17-го студента, "Enter" - завершение программы Самокаткин С.С. Введите оценки студента (всего 4) 5 3 3 3 Введите Ф.И.О. 18-го студента, "Enter" - завершение программы Самолеткин С.С. Введите оценки студента (всего 4) 2 3 5 4 Введите Ф.И.О. 19-го студента, "Enter" - завершение программы Самоходкин С.С. Введите оценки студента (всего 4) 5 2 3 4 Введите Ф.И.О. 20-го студента, "Enter" - завершение программы Самоучкин С.С. Введите оценки студента (всего 4) 3 3 3 4 Введите Ф.И.О. 21-го студента, "Enter" - завершение программы
Самоходкин С.С. Самолеткин С.С. Самокаткин С.С. Самострелкин С.С. Самоделкин С.С. Петрук П.П. Иванчук И.И. Петренко Петров П.П. Иванов И.И. Нажмите любую клавишу...
|
Варианты задания.
Исключить из списка элементы, относящиеся к учащимся, у которых:
1) Средний балл меньше среднего балла группы.
2) Средний балл меньше 4,5.
3) Средний балл больше 4.
4) Все оценки 5.
5) Одна оценка 4, а остальные - 5.
6) Оценка, полученная на первом экзамене - 2.
7) Оценка, полученная на втором экзамене - 5.
8) Нет удовлетворительных и неудовлетворительных оценок.
9) Больше одной оценки 2.
10) Одна оценка 3, а остальные 4 и 5.
11) Одна оценка 5, а остальные 4 .
12) Оценки только 4 и 5.
13) Больше одной оценки 3.
14) Две оценки 3.
15) Одна оценка 4, а остальные 3.
16) Все оценки 3.
17) Оценки 3 и 4.
18) Все оценки 4.
19) Оценка, полученная на первом экзамене - 3.
20) Оценки за первый и третий экзамен 3.
21) Одна оценка 5, а остальные 3.
22) Только одна оценка 5.
23) Две оценки 5, а остальные 2.
24) Одна оценка 2, а остальные 5.
Распечатать оставшийся список.
Лабораторная работа № 14.
Работа со списками.
Цель работы:
1. Закрепить навыки работы с исключением элементов из списка.
2. Ознакомиться с возможностью добавления элементов в список.
Постановка задачи:
Подготовить данные об абитуриентах, поступающих в институт. Информацию о каждом абитуриенте оформить в вид записи со следующими полями:
1.ФИО.
2. Год рождения.
3. Год окончания школы.
4. Оценки в аттестате.
5. Оценки вступительных экзаменов (3).
Оформить информацию в виде внешнего файла.
Занести информацию из внешнего файла в однонаправленный список.
Обработать список согласно варианту.
1. Исключить из списка все элементы, удовлетворяющие условию, заданному в варианте и распечатать полученный список.
2. Добавить N элементов в начало (конец) списка согласно конкретному варианту и распечатать полученный список.
Содержание отчета:
-
Постановка задачи.
-
Тексты программ и результаты их выполнения.
Образец выполнения работы.
Лабораторная работа № 14.
Работа со списками.
Цель работы:
1. Закрепить навыки работы с исключением элементов из списка.
2. Ознакомиться с возможностью добавления элементов в список.
Постановка задачи:
Подготовить данные об абитуриентах, поступающих в институт. Информацию о каждом абитуриенте оформить в вид записи со следующими полями:
1.ФИО.
2. Год рождения.
3. Год окончания школы.
4. Оценки в аттестате.
5. Оценки вступительных экзаменов (3).
Оформить информацию в виде внешнего файла.
Занести информацию из внешнего файла в однонаправленный список.
Обработать список согласно варианту.
1. Исключить из списка все элементы, удовлетворяющие условию, заданному в варианте и распечатать полученный список.
2. Добавить N элементов в начало (конец) списка согласно конкретному варианту и распечатать полученный список.
Вариант задания:
-
Все оценки 4.
-
Добавить в список элементы, относящиеся к абитуриентам, у которых :
все оценки 3 за экзамены и отличный аттестат.
Текст программы:
{Заполнение внешнего файла данными, вводимыми с клавиатуры}
Program P8_5_2;
Uses CRT;
Const
GradMarks=5; {количество оценок в аттестате}
ExamenMarks=3; {количество оценок на экзамене}
Type
Data = Record
Name:String[20]; {Имя}
BirthDate,GradDate:Integer; {год рождения, год окончания школы}
SchoolGrad: Array[1..GradMarks] of Byte; {оценки в аттестате}
ExamGrad: Array[1..ExamenMarks] of Byte; {оценки на экзамене}
End;
Var
Telega: Data;
FileOfData: File of Data ;
(* Процедура заполнения файла 'data.dat' *)
Procedure Initialising;
Var i,y:Integer;
Label
Exits;
Begin
Assign(FileOfData,'data.dat');
ReWrite(FileOfData);
i:=1;
While True Do Begin
WriteLn('__________ Д А Н Н Ы Е ',i,' -ГО А Б И Т У Р И Е Н Т А___________');
WriteLn;
With Telega Do Begin
WriteLn('Введите Ф.И.О. абитуриента:');
WriteLn('"Enter"-завершение программы');
ReadLn(Name);
If (Name='') Then Goto Exits;
WriteLn('Введите год рождения абитуриента:');
ReadLn(BirthDate);
WriteLn('Введите год окончания школы абитуриентом:');
ReadLn(GradDate);
WriteLn('_______Введите оценки из аттестата абитуриента_______');
WriteLn('всего ',GradMarks,' штук');
WriteLn;
For y:=1 to GradMarks Do Begin
ReadLn(SchoolGrad[y]);
End;
WriteLn('Введите оценки, полученные абитуриентом на экзамене:');
WriteLn('Всего ',ExamenMarks,' штук');
WriteLn;
For y:=1 to ExamenMarks Do Begin
ReadLn(ExamGrad[y]);
End;
End;
Write(FileOfData,Telega);
inc(i);
End;
Exits: End;
{**************** Тело программы ***************}
Begin
Initialising;
Close(FileOfData);
End.
Результат работы программы:
__________ Д А Н Н Ы Е 1 -ГО А Б И Т У Р И Е Н Т А___________
Введите Ф.И.О. абитуриента: "Enter"-завершение программы Иванов И.И. Введите год рождения абитуриента: 1970 Введите год окончания школы абитуриентом: 1988 _______Введите оценки из аттестата абитуриента_______ всего 5 штук
5 5 5 5 5 Введите оценки, полученные абитуриентом на экзамене: Всего 3 штук
4 4 4 __________ Д А Н Н Ы Е 2 -ГО А Б И Т У Р И Е Н Т А___________
Введите Ф.И.О. абитуриента: "Enter"-завершение программы Петров Введите год рождения абитуриента: 1971 Введите год окончания школы абитуриентом: 1989 _______Введите оценки из аттестата абитуриента_______ всего 5 штук
5 5 5 5 5 Введите оценки, полученные абитуриентом на экзамене: Всего 3 штук
3 3 3 __________ Д А Н Н Ы Е 3 -ГО А Б И Т У Р И Е Н Т А___________
Введите Ф.И.О. абитуриента: "Enter"-завершение программы Сидоров С.С. Введите год рождения абитуриента: 1972 Введите год окончания школы абитуриентом: 1990 _______Введите оценки из аттестата абитуриента_______ всего 5 штук
4 3 5 4 5 Введите оценки, полученные абитуриентом на экзамене: Всего 3 штук
3 2 4 __________ Д А Н Н Ы Е 4 -ГО А Б И Т У Р И Е Н Т А___________
Введите Ф.И.О. абитуриента: "Enter"-завершение программы Васильев В.В. Введите год рождения абитуриента: 1973 Введите год окончания школы абитуриентом: 1991 _______Введите оценки из аттестата абитуриента_______ всего 5 штук
5 4 3 4 3 Введите оценки, полученные абитуриентом на экзамене: Всего 3 штук
4 4 4 __________ Д А Н Н Ы Е 5 -ГО А Б И Т У Р И Е Н Т А___________
Введите Ф.И.О. абитуриента: "Enter"-завершение программы Сергеев С.С. Введите год рождения абитуриента: 1974 Введите год окончания школы абитуриентом: 1992 _______Введите оценки из аттестата абитуриента_______ всего 5 штук
5 5 5 5 5 Введите оценки, полученные абитуриентом на экзамене: Всего 3 штук
3 3 3 __________ Д А Н Н Ы Е 6 -ГО А Б И Т У Р И Е Н Т А___________
Введите Ф.И.О. абитуриента: "Enter"-завершение программы Юрьев Ю.Ю. Введите год рождения абитуриента: 1974 Введите год окончания школы абитуриентом: 1994 _______Введите оценки из аттестата абитуриента_______ всего 5 штук
5 5 5 5 5 Введите оценки, полученные абитуриентом на экзамене: Всего 3 штук
3 5 5 __________ Д А Н Н Ы Е 7 -ГО А Б И Т У Р И Е Н Т А___________
Введите Ф.И.О. абитуриента: "Enter"-завершение программы Ильин И.И. Введите год рождения абитуриента: 1975 Введите год окончания школы абитуриентом: 1993 _______Введите оценки из аттестата абитуриента_______ всего 5 штук
4 4 4 3 3 Введите оценки, полученные абитуриентом на экзамене: Всего 3 штук
3 3 3 __________ Д А Н Н Ы Е 8 -ГО А Б И Т У Р И Е Н Т А___________
Введите Ф.И.О. абитуриента: "Enter"-завершение программы Михайлов М.М. Введите год рождения абитуриента: 1976 Введите год окончания школы абитуриентом: 1998 _______Введите оценки из аттестата абитуриента_______ всего 5 штук
4 4 4 5 4 Введите оценки, полученные абитуриентом на экзамене: Всего 3 штук
4 4 4 __________ Д А Н Н Ы Е 9 -ГО А Б И Т У Р И Е Н Т А___________
Введите Ф.И.О. абитуриента: "Enter"-завершение программы Савельев С.С. Введите год рождения абитуриента: 1977 Введите год окончания школы абитуриентом: 1999 _______Введите оценки из аттестата абитуриента_______ всего 5 штук
5 5 5 5 5 Введите оценки, полученные абитуриентом на экзамене: Всего 3 штук
3 3 3 __________ Д А Н Н Ы Е 10 -ГО А Б И Т У Р И Е Н Т А___________
Введите Ф.И.О. абитуриента: "Enter"-завершение программы Николаев Н.Н. Введите год рождения абитуриента: 1979 Введите год окончания школы абитуриентом: 1997 _______Введите оценки из аттестата абитуриента_______ всего 5 штук
4 5 4 4 4 Введите оценки, полученные абитуриентом на экзамене: Всего 3 штук
4 4 4 __________ Д А Н Н Ы Е 11 -ГО А Б И Т У Р И Е Н Т А___________
Введите Ф.И.О. абитуриента: "Enter"-завершение программы
|