Лабораторная работа № 10 Динамические списки с одной связью
Общие сведения
Для выполнения лабораторной работы необходимо изучить теоретический материал по следующим разделам:
1)переменные типа указатель;
2)динамические переменные;
3)размещение и удаление динамических переменных;
4)динамические списки с одной связью;
5)методы реализации базовых операций с динамическими списками.
Задание
При решении задачи, указанной в варианте задания следует составить программу, которая:
1)считывает содержимое исходного файла в память, размещая данные в односвязанном динамическом списке;
2)распечатывает исходные данные на экране;
3)просматривает и модифицирует список, выполняя действия, необходимые для решения задачи;
4)выводит полученные результаты на экран и, если это предусмотрено в задании, записывает в новый файл на диске;
5)удаляет динамический список;
6)закрывает файлы и заканчивает работу.
Требования к выполнению задания
При решении задачи необходимо придерживаться следующих основных требований:
1)для хранения исходных данных должен использоваться текстовый или типизированный файл (тип элементов файла оговаривается в задаче), который требуется быть заранее подготовить;
2)при разработке программы не следует делать предположений о размере исходного файла и числе его элементов;
3)исходные данные могут читаться из файла только один раз;
4)данных в основной памяти должны размещаться в динамическом списке с одной связью;
5)тип информационного поля элемента списка должен соответствовать типу элемента исходного
файла;
6)при необходимости разрешается создавать вспомогательные динамические списки;
7)результаты, полученные в процессе работы программы, должны выводиться на экран;
8)при разработке тестов необходимо предусмотреть проверку различных режимов работы программы;
9)решение отдельных подзадач решаемой задачи следует реализовать с помощью подпрограмм. Оформление программы должно соответствовать "Общим требованиям к оформлению программ".
Неправильно оформленные программы не рассматриваются.
Примечания
Динамический список с одной связью представляет собой последовательность элементов, каждый из которых (кроме последнего) хранит информацию о местоположении следующего элемента списка. Каждый элемент списка реализуется в виде записи, которая включает два поля: info – информационное поле, предназначенное для хранения элемента данных, и next – поле связи, содержащее адрес следующего элемента списка. Поле связи последнего элемента списка должно содержать пустой указатель nil. Тип информационного поля определяется условиями задачи, а тип поля связи представляет собой указатель на элемент списка.
Динамический список одной связью может быть изображен в виде следующей схемы:
Head |
Элементы списка |
|
Info |
Next |
|
Info |
Next |
… |
Info |
Next |
|
nil |
Переменная Head является переменной типа указатель, которая предназначена для сохранения ссылки на первый элемент списка.
Пример выполнения задания Задание
В исходном файле расположении последовательность записей. Каждая запись представляет собой элемент ведомости на выдачу зарплаты сотрудников предприятия и содержит фамилию и инициалы сотрудника, а также величину заработной платы, указанную в рублях и копейках. Записи, находящиеся в файле, упорядочены по фамилии сотрудника. Вывести в выходной текстовый файл перечень сотрудников и их зарплат, упорядоченный по убыванию значения заработной платы. Последняя строка выходного файла должна содержать дополнительную запись вида: Итого: <значение общей суммы выплат>.
program Lab10; |
procedure WriteList(P:PNode;var f:tex |
type |
var |
TItem=record |
SumOfPay:real; |
Name:string[13]; |
begin |
Pay:real; |
SumOfPay:=0; |
end; |
while P<>nil do begin |
TItemsFile=file of TItem; |
with P^.Info do begin |
PNode=^TNode; |
writeln(f,Name:12,' ',Pay:8:2); |
TNode=record |
SumOfPay:=SumOfPay+Pay; |
Info:TItem; |
end; |
Next:PNode |
P:=P^.Next; |
end; |
end; |
procedure InitList(var Head:PNode); |
writeln(f,'Итого: ',SumOfPay:10:2); |
begin |
end; |
Head:=nil; |
procedure DeleteList(var Head:PNode); |
end; |
var |
procedure PrintList(P:PNode); |
P,Q:PNode; |
begin |
begin |
if P=nil then write('List empty'); |
P:=Head; |
while P<>nil do begin |
while P<>nil do begin |
with P^.Info do writeln(Name:12,' ',Pay:8:2); |
Q:=P^.Next; |
P:=P^.Next; |
Dispose(P); |
end; |
P:=Q; |
writeln; |
end; |
end; |
Head:=P; |
procedure InsertToHead(AItem:TItem;var Head:PNode); |
end; |
var |
var |
Q:PNode; |
i:integer; |
begin |
Head:PNode; |
New(Q); |
Memory:longint; |
Q^.Next:=Head; |
f:text; |
Q^.Info:=AItem; |
t:TItemsFile; |
Head:=Q; |
P:TItem; |
end; |
begin |
procedure InsertAndSort(Item:TItem;var Head:PNode); |
assign(t,'input.dat'); |
var |
reset(t); |
P,Q,R:PNode; |
assign(f,'output.dat'); |
begin |
rewrite(f); |
if (Head^.Info.Pay<Item.Pay) or (Head=nil) then |
InitList(Head); |
InsertToHead(Item,Head) |
while not eof(t) do begin |
else begin |
read(t,P); |
R:=Head; |
InsertAndSort(P,Head); |
P:=Head^.Next; |
end; |
while (P<>nil) and (P^.Info.Pay>=Item.Pay) do begin |
PrintList(Head); |
R:=P; |
WriteList(Head,f); |
P:=P^.Next; |
DeleteList(Head); |
end; |
close(f); |
New(Q); |
close(t) |
Q^.Info:=Item; |
end. |
Q^.Next:=R^.Next; |
|
R^.Next:=Q |
|
end |
|
end; |
|