Материал: Лабораторная работа №10 Односвязные списки, Поиск, Сортировка
Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»
end;{if} //удаляем узел dispose(AHead);
//запоминаем текущий узел
AHead:=CurNode; end;{while}
end;{DestroyList}
procedure ProcessList(AHead:PNode; ANodeProc:TProcessNode); begin
//обход списка начиная с первого узла while AHead<>nil do
begin
ANodeProc(AHead^.data); //процедура обработки данных узла
AHead:=Next(AHead); end;{while}
end;{ProcessList}
function SearchMin(AHead:PNode; CompareProc:TCompareProc):PNode; var minNode:PNode;
begin minNode:=AHead; AHead:=Next(AHead);
//обход списка начиная со второго узла while AHead<>nil do
begin
if CompareProc(minNode^.data, AHead^.data)>=0 then minNode:=AHead;
AHead:=Next(AHead); end;{while}
Result:=minNode; end;{SearchMin}
function SearchMax(AHead:PNode; CompareProc:TCompareProc):PNode; var minNode:PNode;
begin minNode:=AHead; AHead:=Next(AHead);
//обход списка начиная со второго узла while AHead<>nil do
begin
if CompareProc(minNode^.data, AHead^.data)<=0 then minNode:=AHead;
AHead:=Next(AHead); end;{while}
Result:=minNode; end;{SearchMax}
function SearchNode(AHead:PNode; data:Pointer; CompareProc:TCompareProc):PNode;
begin Result:=nil;
//обход списка начиная с первого узла while AHead<>nil do
//проверка узла на соответствие критерию поиска if CompareProc(AHead^.data, data)=0 then
begin Result:=AHead; break;
Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»
end
else AHead:=Next(AHead); end;{SearchNode}
function SearchNodes(AHead:PNode; data:Pointer; CompareProc:TCompareProc):PNode;
var TempList, Node:PNode; begin
TempList:=nil; //список найденных узлов
//обход списка, начиная с первого узла while AHead<>nil do
begin
//проверка узла на соответствие критерию поиска if CompareProc(AHead^.data, data)=0 then
begin
//создаем новый узел, копируем указатель на данные узла
Node:=NewNode(AHead^.data);
//вставка узла в список найденных узлов
InsertBefore(TempList, Node); end;{if}
AHead:=Next(AHead); end;{while AHead}
Result:=TempList; end;{SearchNodes}
procedure InsertionSort(var AHead:PNode; CompareProc:TCompareProc);
var TempList:PNode;
CurNode, Cur, PrevNode:PNode; begin
{создаем список, содержащий минимальный элемент исходного cписка}
TempList:=SearchMin(AHead, CompareProc);
//удаляем найденный минимальный элемент из исходного списка
TempList:=DeleteNode(AHead, TempList);
//обход исходного списка начиная с первого элемента while AHead<>nil do
begin
{удаляем текущий элемент из исходного списка и переходим к следующему элементу}
Cur:=AHead;
AHead:=AHead^.next;
Cur^.next:=nil;
CurNode:=TempList; //установка на начало списка
PrevNode:=CurNode;
while CurNode<>nil do //поиск места вставки begin
if CompareProc(CurNode^.data, Cur^.data)>=0 then begin
{если вставляемый элемент "меньше" текущего, то вставляем его}
InsertBefore(PrevNode, Cur); break;
Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»
end{if} else
begin
PrevNode:=CurNode; //запоминаем текущий узел
CurNode:=Next(CurNode);//переходим к следующему узлу end{else}
end;{ while CurNode}
{вставка элемента в конец списка}
if CurNode=nil then InsertBefore(PrevNode, Cur); end;{while AHead}
//указатель на отсортированный список
AHead:=TempList; end;{InsertionSort}
end.{Lists}