ЛАБОРАТОРНАЯ РАБОТА №25
ТЕМА: ДВУНАПРАВЛЕННЫЕ СВЯЗАННЫЕ СПИСКИ.
Задание на лабоpатоpную pаботу
Проект (Project1) должен включать в себя два модуля Unit1 и Unit2.
Первый модуль (Unit1) обеспечивает интерфейс в виде оконной формы (приложение Form1).
Вид оконного интерфейса представлен на рисунке
Второй модуль (Unit2) – это набор методов (процедур) редактирования списка (приложение Unit.pas), интерфейсная секция такого модуля должна содержать не менее 5-ти процедур согласно вариантов заданий:
Варианты заданий.
3-4 Построить список. 1-2 Построить список.
Вывести список на экран. Вывести список на экран.
Уничтожить список. Уничтожить список.
"Склеить" два списка. Добавить узел к "хвосту" списка.
Добавить узел к "голове" списка. Удалить первый узел списка.
7-8 Построить список. 5-6 Построить список.
Вывести список на экран. Вывести список на экран.
Уничтожить список. Уничтожить список.
Удалить последний узел списка. Определить длину списка.
Добавить узел к "голове" списка. Удалить первый узел списка.
11-12 Построить список. 9-10 Построить список.
Вывести список на экран. Вывести список на экран.
Уничтожить список. Уничтожить список.
Удалить последний узел списка. Добавить узел к "голове" списка.
Добавить узел после указанного Удалить узел с указанным
номера. номером.
15-16 Построить список. 13-14 Построить список.
Вывести список на экран. Вывести список на экран.
Уничтожить список. "Склеить" два списка.
Добавить узел к "хвосту" списка. Удалить узел с указанным
Отсортировать список в порядке номером.
возрастания Определить узел с заданным
значений какого-либо поля записи. значением какого-либо поля записи.
19-20 Построить список. 17-18 Построить список.
Вывести список на экран. Вывести список на экран.
Уничтожить список. Определить узел с заданным
Удалить последний узел списка. значением какого-либо поля записи.
Удалить первый узел списка. Добавить узел к "хвосту" списка.
Удалить первый узел списка.
21-22 Построить список. 25-26 Построить список.
Вывести список на экран. Вывести список на экран.
Уничтожить список. Уничтожить список.
Удалить последний узел списка. Добавить узел к "хвосту" списка.
Удалить первый узел списка. Удалить первый узел списка.
23-24 Построить список. Удалить последний узел списка
Вывести список на экран. Удалить первый узел списка.
Уничтожить список.
Тип записи взять из файла “ВАРИАНТЫЗАПИСЕЙ”
в соответствии с номером по списку в журнале группы.
Структура списка должна иметь следующий вид (рис. 3),
либо согласно примеру в файле “Delphi_списки2_методика”:
Под пустым списком следует понимать служебную структуру данных типа запись, содержащую поля указателей на начало и конец линейного списка, а также поле-счетчик узлов этого списка. При этом поля указателей еще не содержат конкретный адрес узла начала и узла конца списка, а лишь проинициализированы безадресным значением nil. В свою очередь поле-счетчик содержит значение 0.
type List= record
head:PtrNode; { указатель начала списка }
tail:PtrNode; { указатель конца списка }
count:integer;
end;
Графически это можно представить как показано на рис.3.1.
|
 |
|
ni l nil
Рис.3
Как следует из раздела 2, каждый узел двунаправленного линейного списка содержит один указатель на следующий узел и один на предыдущий. В последнем узле списка указатель на следующий узел содержит значение nil, и соответственно в первом узле списка указатель на предыдущий узел также содержит значение nil. Для реализации этих целей используем следующие структурные построения данных:
type PtrStud=^student;
student= record { информационная запись }
name: string [20]; age:integer; group: string [10]
end;
PtrNode=^node;
node= record
info:student;
prev:PtrNode; {указатель на предыдущий
next:PtrNode; и на последующие узлы списка }
end;
List= record
head:PtrNode;
tail:PtrNode;
count:integer;
end;
Proc= procedure(x:ptrnode);
Для построения списка следует выполнить итерационную процедуру связывания структурированных узлов, посредством инициализации их полей prev и next:
var current:ptrnode; {указатель на текущий узел}
listfile:file of student;
list0:list;
procedure create_list;
begin
reset(listfile);
{1} new(current); {выделена память под первый узел списка}
read(listfile,current^.info); {чтение из файла информации
по первому студенту в узел 1}
list.count:=1;
{2} current^.prev:=nil;{поле prev (указатель на предыдущий
узел) первого узла принимает значение nil }
list0.head:=current; {указатель начала списка поставлен на
текущий первый узел}
while not eof(listfile) do
begin
{3} new(current^.next);{выделить память для следующего узла
по адресу, записанному в поле next текущего узла}
read(listfile,current^.next^.info);
{4} current^.next^.prev:=current; {инициализируем поле prev
второго узла, записывая в него адрес первого узла, на который
указывает указатель current(связывание второго узла с первым по полю prev)}
inc(list0.count);
{5} current:=current^.next;{сделать следующий(второй) узел текущим (перемещаем указатель current на следующий узел)}
end;
list0.tail:=current;{указатель конца списка ставим на
последний узел}
current^.next:=nil;{поле next последнего узла списка
принимает значение nil}
close(listfile);
readkey;
end;
На рис.3.2 графически интерпретированы действия операторов программы.
| |||||
 | |||||
 | |||||
|
{3}
 |  | ||||
 |
{4}
 |
|
{5}
 |  |
|
|
 | |||||
 | |||||
 |
Рис.3.2
Процедуру построения списка следует дополнить процедурой инициализации указателей начала и конца списка.
procedure init_list;
begin
list0.head:=nil; list0.tail:=nil; list0.count:=0;
end;