Материал: Лабораторная работа №10 Односвязные списки, Поиск, Сортировка

Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»

3.Напишите функцию Last для нахождения последнего элемента списка. Добавьте ее в модуль Lists. Напишите пример программы использующий эту функцию.

4.Перепишите программу из листинга 2 лабораторной работы №5 с использованием односвязных списков. Добавьте в программу следующие возможности:

−удаление произвольной записи из таблицы;

−сортировка таблицы по столбцу фамилия;

−поиск записи по фамилии, причем если число таких записей более одной, то должны выводится все записи;

−вывод только студентов заданной группы;

−сохранение списка в типизированный файл;

−загрузка списка из типизированного файла.

Поместите основные подпрограммы в модуль Tables. Реализуйте меню. Каждую функцию программы реализуйте в виде отдельной подпрограммы.

Вопросы к лабораторной работе

1.Что такое односвязный список?

2.Что такое узел? Как описывается узел односвязного списка?

3.Объясните алгоритм вставки узла в односвязный список.

4.Объясните алгоритм удаления узла из односвязного списка.

5.Объясните алгоритм сортировки вставками.

6.Объясните алгоритм прохождения односвязного списка.

7.Для чего используется процедура Move?

Справочные таблицы

Приложение А – Модуль Lists

Листинг 3 – Модуль для работы с односвязными списками

unit Lists;

interface

type PNode=^TNode;

//структура описывающая узел односвязного списка

TNode=record

next:PNode; //указатель на следующий узел data:pointer; //указатель на данные

end;

{подпрограмма для обработки данных узла ВХОДНЫЕ ПАРАМЕТРЫ

P - указатель на данные узла} TProcessNode = procedure (P:Pointer);

Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»

{функция для сравнения двух узлов ВХОДНЫЕ ПАРАМЕТРЫ

P1, P2 - указатели на данные узлов

Результат функции

1 - если P1>P2

-1 - если P1<P2

0 - если P1=P2

}

TCompareProc = function (P1, P2:Pointer):ShortInt;

{возвращает указатель на вновь созданный узел ВХОДНЫЕ ПАРАМЕТРЫ

P - указатель на данные узла} function NewNode(Data:pointer):PNode;

{вставка узла InsNode после узла ANode ВХОДНЫЕ ПАРАМЕТРЫ

Результат функции

возвращается указатель на вставленный узел}

function InsertBefore(var ANode:PNode; InsNode:PNode):PNode;

{удаление узла после узла ANode, ВХОДНЫЕ ПАРАМЕТРЫ

ANode - узел, после которого необходимо удалить узел Результат функции возвращает указатель на удаленный узел}

function DeleteBefore(ANode:PNode):PNode;

{удаление заданного узла из списка, ВХОДНЫЕ ПАРАМЕТРЫ

AHead - первый узел списка ANode - удаляемый узел Результат функции

возвращает указатель на удаленный узел}

function DeleteNode(var AHead:PNode; ANode:PNode):PNode;

{переход к следующему узлу ВХОДНЫЕ ПАРАМЕТРЫ

ANode - узел списка Результат функции указатель на следующий узел}

function Next(ANode:PNode):PNode;

{переход к предыдующему узлу ВХОДНЫЕ ПАРАМЕТРЫ

ANode - узел списка Результат функции

указатель на предыдующий узел} function Prev(AHead, ANode:PNode):PNode;

{удаление списка ВХОДНЫЕ ПАРАМЕТРЫ

AHead - первый узел списка

ANodeProc - процедура отвечающая за удаление данных узла,

Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»

если данные не нужно удалять, то необходимо в качестве параметра передать nil}

procedure DestroyList(var AHead:PNode; ANodeProc:TProcessNode);

{обработка элементов списка ВХОДНЫЕ ПАРАМЕТРЫ

AHead - первый узел списка

ANodeProc - процедура отвечающая за обработку узла

Выполняется обход всех элементов списка с вызовом для каждого элемента процедуры ANodeProc}

procedure ProcessList(AHead:PNode; ANodeProc:TProcessNode);

{поиск минимального элемента ВХОДНЫЕ ПАРАМЕТРЫ

AHead - первый узел списка CompareProc - функция сравнения узлов

Результат функции указатель на "минимальный" узел}

function SearchMin(AHead:PNode; CompareProc:TCompareProc):PNode;

{поиск максимального элемента ВХОДНЫЕ ПАРАМЕТРЫ

AHead - первый узел списка CompareProc - функция сравнения узлов

Результат функции указатель на "максимальный" узел}

function SearchMax(AHead:PNode; CompareProc:TCompareProc):PNode;

{сортировка списка методом вставок ВХОДНЫЕ ПАРАМЕТРЫ

AHead - первый узел сортируемого списка CompareProc - функция сравнения узлов

ВЫХОДНЫЕ ПАРАМЕТРЫ

AHead - первый узел отсортированного списка} procedure InsertionSort(var AHead:PNode; CompareProc:TCompareProc);

{поиск элемента списка ВХОДНЫЕ ПАРАМЕТРЫ

AHead - первый узел списка

data - указатель на некоторые данные используемые параметром CompareProc, если данные не нужны, то nil

CompareProc - функция сравнения узлов, для узла соответствующего критерию поиска должна возвращать 0

Результат функции

указатель на найденный узел или nil если узел не найден} function SearchNode(AHead:PNode; data:Pointer; CompareProc:TCompareProc):PNode;

{поиск нескольких элементов списка соответствующих критерию поиска ВХОДНЫЕ ПАРАМЕТРЫ

AHead - первый узел списка

Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»

data - указатель на некоторые данные используемые параметром

CompareProc,

если данные не нужны, то nil CompareProc - функция сравнения узлов, для узла

соответствующего критерию поиска должна возвращать 0

Результат функции

указатель на список найденных узлов или nil если не найден ни один узел

При формировании результата функцией SearchNodes создается новый список, причем указатели на данные копируются в новый список. При удалении списка с результатами поиска процедурой DestroyList целесообразно в качестве параметра ANodeProc этой подпрограммы использовать nil. Иначе данные содержащиеся в исходном списке могут быть уничтожены!}

function SearchNodes(AHead:PNode; data:Pointer; CompareProc:TCompareProc):PNode;

implementation

function NewNode(Data:pointer):PNode; begin

Result:=new(PNode);

Result^.data:=Data;

Result^.next:=nil; end;{NewNode}

function InsertBefore(var ANode:PNode; InsNode:PNode):PNode; begin

//если список не содержит узлов if ANode=nil then ANode:=InsNode

else //если вставляемый узел не пустой if InsNode<>nil then

begin InsNode^.next:=ANode^.next; ANode^.next:=InsNode;

end;{if InsNode} Result:=InsNode;

end;{InsertBefore}

function DeleteBefore(ANode:PNode):PNode; begin

if ANode<>nil then

if ANode^.next<>nil then //если удаляемый узел существует begin

Result:=ANode^.next;

ANode^.next:=ANode^.next^.next;

Result^.next:=nil; end{if ANode^.next}

else Result:=nil else Result:=nil; end;{DeleteBefore}

function Next(ANode:PNode):PNode; begin

if ANode<>nil then Result:=ANode^.next else Result:=nil;

Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»

end;{Next}

function DeleteNode(var AHead:PNode; ANode:PNode):PNode; var CurNode:PNode;

begin Result:=nil;

if AHead<>ANode then begin

CurNode:=AHead;

while CurNode<>nil do //поиск узла для удаления begin

if CurNode^.next=ANode then begin

result:=ANode;

//узел найден, удаляем

DeleteBefore(CurNode);

break; end;{if}

CurNode:=Next(CurNode); end;{while}

end else

begin AHead:=Next(AHead); Result:=ANode; ANode^.next:=nil;

end; end;{DeleteNode}

function Prev(AHead, ANode:PNode):PNode; begin

Result:=nil;

//поиск узла указатель next которого равен ANode while AHead<>nil do

begin

if AHead^.next=ANode then begin

Result:=AHead;

break; end;{if}

AHead:=Next(AHead); end;{while}

end;{Prev}

procedure DestroyList(var AHead:PNode; ANodeProc:TProcessNode); var CurNode:PNode;

begin

//начало списка

CurNode:=AHead;

//обход списка начиная с первого узла while CurNode<>nil do

begin //следующий узел

CurNode:=Next(CurNode);

//если задана процедура удаления данных узла, то выполняем ее if Assigned(ANodeProc) then

begin ANodeProc(AHead^.data); AHead^.data:=nil;