Тема 2 5. АЛГОРИТМЫ ПОИСКА И СОРТИРОВКИ НА СВЯЗАНЫХ ЛИНЕЙНЫХ СПИСКАХ

в однонаправленных списках
Поиск заданного элемента
Поиск элемента после заданного
Сортировка однонаправленных

списков
Пузырьковая сортировка
Сортировка слиянием

в ячейках списка
Tinf=record;
информационные поля:
Key:Tkey; // поле

ключа как одно из полей
end;
//рекурсивный тип
Tsel=^sel;
sel=Record
Inf:TInf; // информация об элементе списка
A:Tsel; //Адрес ячейки такого же типа
end;

Var
sp,sp1,spk:Tsel; //указатели на ячейки списка

sp1,spk,sp:Tsel;
constructor create;
procedure

Add1(Inf:Tinf);
procedure Addk(Inf:Tinf);
procedure Read1(Inf:Tinf);
Function Tlist.Poisk(K:TKey):Tsel;
. . . . . . . . . . . . .
procedure Print;
end;
constructor Tlist.create;
begin
inherited create;
sp1:=nil; spk:=nil;
end;

Будем добавлять в этот класс новые методы

поле Inf.key
Function Tlist.Poisk(K:TKey):Tsel;
begin
if sp1=Nil then Resalt:=Nil else
begin//если

список не пуст
sp:=sp1;
While(sp^.Inf.key<>K) and (sp^.A<>Nil)
do sp:=sp^.A;

if sp^.Inf.key<>K then Result:=Nil
else Result:=sp
end;
end;

I1

A1

I.key=k

A2

Ik-1

Ak-1

Ik

nil

….

sp1

spk

sp

spnil then Write(sp.inf);
. . . .
List.Free;

содержащий заданный ключ K в информационном поле Inf.key
Function Tlist.PoiskAfter(k:Tkey):Tsel;

begin
if sp1^.A=Nil then Resalt:=Nil
else
begin//если элементов больше чем один
sp:=sp1;
While(sp^.A^.Inf.key<>k) and (sp^.A^.A<>Nil)
do sp:=sp^.A;
if sp^.A^.Inf.key<>k then Result:=Nil
else Result:=sp;
end;
end;

sp

c меткой

sp:=List.poiskAfter(kl); //найти

If spnil then Write(sp.A.inf);
. . . .
List.Free;

Эффективность

O(n),
т.е. Коп<=C*n при n, C – не зависит от n

по ключу.

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

соседних элементов.

Поменять местами два соседних элемента в однонаправленном списке можно двумя способами:

С помощью обмена информации
С помощью обмена адресами

// 1
sp^.Inf:=sp^.A^.Inf; // 2
sp^.A^.inf:=Inf; // 3

end;

…

Ik

Ak

Ik-1

Ak-1

Ik

nil

….

spk

sp

Inf

sp1

1

2

3

begin
sp:=spi^.A^.A; // 1
spi^.A^.A:=sp^.A; // 2
sp^.A:=spi^.A; // 3
spi^.A:=sp;

// 4
end;

Inf

A

Inf

Inf

Inf

A

A

A

sp

1

4

2

3

spi

. end;
Var spt:Tsel;
begin
spt:=Nil;
Repeat
sp:=sp1;
While sp^.Aspt do begin
if sp^.Inf.key>sp^.A^.Inf.key

then RevInf(sp);
sp:=sp^.A;
end;
spt:=sp;//запомнили последний
Until sp1^.A=spt;
end;

. . . end;
Var spt:Tsel;
begin
spt:=Nil;
Repeat

sp:=sp1;
While sp^.A^.A<>spt do
begin
if sp^.A^.Inf.key>sp^.A^.A^.Inf.key
then RevAfter(sp);
sp:=sp^.A;
end;
spt:=sp^.A;//запомнили последний
Until sp1^.A^.A=spt;
end;

//создать список безметки
Заполнить список, например из файла
List.Add1(List.sp1.Inf);

//добавить метку
sp:=List.SortBublAdr(kl); //сортировать
List.Read1(List); //удалить метку

. . . .
List.Free;

Эффективность O(n),
т.е. Коп<=C*n при n, C – не зависит от n

– отсортирована

Элементарная подзадача: (Slip)
Слияние двух отсортированных очередей в одну отсортированную

Рекурсивное

соотношение:

Sorsl[trn(1,k)]=Slip[Sorsl[trn(1,k/2)], Sorsl[trn(k/2+1,k)]

Div2sp(tp,tq,tr);

Sorsl(tq);
Sorsl(tr);
Slip(tq,tr,tp);
end;
end;

Сначала весь список будет разбит на списки по одному элементу, затем они будут сливаться в списки по 2 упорядоченных, затем по 3-4 упорядоченных…-пока не сольются в один упорядоченный.

две отсортированных в порядке возрастания очереди (tq, tr:Tlist)
Схему алгоритма

их слияния в одну отсортированную очередь tp:Tlist можно представить в виде

tp

tq

tr

and (tr.sp1Nil) do
if tq.sp1.Inf.key

then begin tq.Read1(Inf); tp.Addk(Inf) end
else begin tr.Read1(Inf); tp.Addk(Inf) end;

while tq.sp1<>nil do
begin tq.Read1(Inf); tp.Addk(Inf); end;

while tr.sp1<>nil do
begin tr.Read1(Inf); tp.Addk(Inf); end;
end;

tq:=Tlist.create;
tr:=Tlist.create;
c:=-1;
While tp.sp1Nil do

begin c:=-c;
tp.Read1(Inf);
If C>0 then tq.Addk(Inf)
else tr.Addk(Inf);
end;
end;

Begin . . . . . End;

Procedure Div2sp(tp:TList;var tq,tr:TList);
Begin . . . . . End;
Procedure Sorsl(var tp:Tlist);
Begin . . . . . End;
begin
Sorsl(self);
end;

constructor create;
procedure Add1(Inf:Tinf);

Procedure Addk(Inf:TInf);
procedure Read1(var Inf:Tinf);
procedure Writ(var stg:Tstringgrid);
procedure Addn(n:word;stg:Tstringgrid);
Procedure SortBublInf;
Procedure Sortslip;
end;

for i:=1 to n do
begin

inf.I1:= stg.cells[1,i];
inf.key:=StrToint(stg.cells[0,i]);
addk(inf);
end;
end;

While sp Nil do
begin k:=k+1;

stg.cells[1,k]:=sp^.Inf.I1;
stg.cells[0,k]:=Inttostr(sp^.Inf.key);
sp:=sp^.A;
end;
end;

n, изменение размера и настройка StringGrid
procedure TForm1.Edit1Change(Sender: TObject);
begin
n:=strtoint(edit1.text);
StringGrid1.RowCount:=n+1;

StringGrid2.RowCount:=n+1;
StringGrid1.Cells[0,0]:='key';
StringGrid1.Cells[1,0]:='I1';
StringGrid2.Cells[0,0]:='key';
StringGrid2.Cells[1,0]:='I1';
end;

TForm1.Button2Click(Sender: TObject);
Begin //Вывод списка
trn.Writ(StringGrid2)
end;

procedure TForm1.Button3Click(Sender: TObject);
Begin //Сортировка
case

RadioGroup1.ItemIndex of
0:trn.SortBublInf;
1:trn.Sortslip;
end;
end;

0:trn.SortBublInf;
1:trn.Sortslip;
2:begin

trn.Add1(trn.sp1.Inf);//добавить метку
trn.SortBublAdr;
trn.Read1(Inf); //убрать метку
end;
end;

end;

отличие от такой же сортировки массива.

Если требуется отсортировать файл

или массив, то его считывают в список, сортируют и отсортированный список снова записывают в файл или массив.

При небольших объемах информации в ячейках сортировка слиянием является одной из самых эффективных.

Если информационные ячейки имеют большой объем, то более эффективной является сортировка обменом ключей.

метод поиска адреса элемента списка, предшествующего тому, который содержит заданный

ключ.

Опишите последовательность действий при замене местами двух соседних элементов в списке методом перестановки адресов и методом обмена информацией.

Напишите метод сортировки стека с меткой методом перестановки адресов.

Напишите метод сортировки стека методом обмена информацией.

Опишите последовательность действий при сортировке стека методом слияния.

Inf.к - учетный номер) из StringGrid1 в стек с меткой,

отсортировать стек методом пузырька с обменом ключами, вывести отсортированный стек в StringGrid2.


Ввести массив записей {a[i]:TInf } (Inf.F - фамилия; Inf.к - учетный номер) из StringGrid, в односвязный список в виде очереди, отсортировать очередь методом слияния, вывести отсортированный список в StringGrid2.
Алгоритмы записи, чтения элементов списка и его сортировки оформить в отдельном модуле в виде методов класса.