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

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

4.изымается первый элемент из исходного списка и вставляется в новый список так, чтобы не нарушить его правильный порядок элементов (т.е. так чтобы после вставки элемента массив остался отсортированным);

5.пункт 4 повторяется до тех пор, пока в исходном списке не останется элементов.

Код реализующий данный алгоритм приведен ниже

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}

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

Примеры программ использующих односвязные списки

В данном разделе приведены некоторые примеры использования односвязных списков. Для работы всех примеров необходимо подключить к проекту модуль Lists. В модуле Lists собраны подпрограммы для работы с односвязными списками.

Демонстрационная программа для модуля Lists

В ниже приведенной программе приведен пример использования некоторых подпрограмм из модуля Lists.

Листинг 1 – Демонстрационная программа

program SList;

{$APPTYPE CONSOLE}

uses SysUtils,

Lists in 'Lists.pas';

var pInt:^integer; Head:PNode=nil; //список

CurNode, Node:PNode; //текущий узел i, elm:integer;

SNode:PNode;

//вспомогательные подпрограммы

//печать данных узла на экран procedure NodePrint(P:Pointer);

begin

if p<>nil then write(Integer(P^), ' '); end;

//удаление целочисленных динамических переменных procedure DestroyData(P:Pointer);

begin

if p<>nil then dispose(p); end;

//сравнение двух целых чисел

function CompareProc(P1, P2:Pointer):ShortInt; begin

if Integer(P1^)>Integer(P2^) then Result:=1 else

if Integer(P1^)<Integer(P2^) then Result:=-1 else Result:=0;

end;

//условие отбора элементов списка

function CompareProc2(P1, P2:Pointer):ShortInt; begin

if Integer(P1^)>Integer(P2^) then Result:=0 else result:=-1;

end;

//сравнение элемента списка с заданным элементом function SearchProc(P1, P2:Pointer):ShortInt;

begin

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

if Integer(P1^)=Integer(P2^) then Result:=0 else result:=-1;

end;

//основная программа begin

writeln('Demo single link list'); //создаем список содержащий 20 узлов //каждый узел содержит целое число randomize;

for i:=1 to 20 do begin

new(pInt);//динамическая переменная типа integer //присваиваем динамической переменной значение pInt^:=random(100); Node:=NewNode(pInt);//создаем новый узел

//вставляем узел в список

if Head=nil then CurNode:=InsertBefore(Head, Node) else CurNode:=InsertBefore(CurNode, Node)

end;

//вывод содержимого списка на экран writeln('Source List'); ProcessList(Head, NodePrint); writeln;

//поиск элемента в списке write('Input element to Search: '); readln(elm);

if SearchNode(Head, @elm, SearchProc)<>nil then writeln('Element [', elm, '] found')

else

writeln('Element [', elm, '] not found');

//удаление элемента из списка write('Input element to delete: '); readln(elm);

SNode:=SearchNode(Head, @elm, SearchProc); if SNode<>nil then

begin

writeln('Node [', elm, '] deleted'); DeleteNode(Head, SNode); ProcessList(Head, NodePrint); writeln;

end else

writeln('Element [', elm, '] not found');

//вывод списка узлов значение которых больше заданной величины write('Input value: ');

readln(elm);

SNode:=SearchNodes(Head, @elm, CompareProc2); if SNode<>nil then

begin

writeln('Search result'); ProcessList(SNode, NodePrint);

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

writeln;

{уничтожение списка с результатами поиска, данные содержащиеся в списке не уничтожаются} DestroyList(SNode, nil);

end else

writeln('Elements not found');

//поиск максимального и минимального значений элементов writeln('Min Value ', Integer(SearchMin(Head,

CompareProc)^.data^));

writeln('Max Value ', Integer(SearchMax(Head, CompareProc)^.data^));

//сортировка списка writeln('Sort List'); InsertionSort(Head, CompareProc); ProcessList(Head, NodePrint); writeln;

//уничтожение списка

DestroyList(Head, DestroyData); writeln('Press Enter to exit'); readln;

end.

Загрузка в список текстового файла

Следующая программа загружает в список содержимое текстового файла.

Листинг 2 – Программа для загрузки текстового файла

program TextList;

{$APPTYPE CONSOLE}

uses SysUtils,

Lists in 'Lists.pas';

//вспомогательные подпрограммы

//печать данных узла на экран procedure NodePrint(P:Pointer);

begin

if p<>nil then writeln(ShortString(P^)); end;

//удаление целочисленных динамических переменных procedure DestroyData(P:Pointer);

begin

if p<>nil then FreeMem(P); end;

//основная программа var F:TextFile;

pStr:pointer;

Buf:string[255]; Head:PNode=nil; //список

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

CurNode, Node:PNode; //текущий узел FileName:string;

begin

writeln('Load TextFile'); write('FileName: '); readln(FileName);

AssignFile(F, FileName); {$I-}

Reset(F);

if IOResult<>0 then Halt(1); {$I+}

while not EOF(F) do begin

//считываем строку из файла во временную переменную readln(F, Buf);

{выделяем память под строку длина строки + 1 байт} GetMem(pStr, Length(Buf)+1);

{копируем строку из временной переменной в динамическую}

Move(Buf, pStr^, Length(Buf)+1);

Node:=NewNode(pStr);//создаем новый узел

//вставляем узел в список

if Head=nil then CurNode:=InsertBefore(Head, Node) else CurNode:=InsertBefore(CurNode, Node)

end;

CloseFile(F);

//вывод содержимого списка на экран

ProcessList(Head, NodePrint);

//уничтожение списка

DestroyList(Head, DestroyData); writeln('Press Enter to exit'); readln;

end.

В приведенной программе для копирования строки использована процедура Move из модуля System. Эта процедура предназначена для копирования данных из одной области памяти в другую и имеет следующий синтаксис.

procedure Move(const Source; var Dest; Count: Integer);

где Source – источник данных (что копировать); Dest – приемник данных (куда копировать);

Count – объем копируемых данных в байтах (сколько копировать).

Задания к лабораторной работе

1.Изучите все подпрограммы модуля Lists и объясните алгоритм их работы. (По согласованию с преподавателем).

2.Наберите и изучите алгоритмы программ приведенных в лабораторной работе.