End else. lptr = ^item; { указатель на элемент списка }

Begin

Begin

Type

Begin

Begin

Begin

Begin

Type

lptr = ^item; { указатель на элемент списка }

item = record { элемент списка }

key: Integer; { ключ }

inf: data; { данные }

next: lptr; { указатель на элемент списка }

end;

Сортировку будем вести по возрастанию ключей. Параметром функции сортировки будет указатель на начало неотсортированного списка, а возвращает функция указатель на начало отсортированного списка. Прежний, несортированный список перестает существовать.

Следующий пример демонстрирует сортировку выборкой. Указатель newh является адресом начала выходного списка, исходно пустого. Во входном списке ищется максимальный элемент. Найденный элемент исключается из входного списка и включается в начало выходного списка. Работа алгоритма заканчивается, когда входной список станет пустым.

{ Сортировка выборкой на 1-связном списке }

function Sort(head: lptr): lptr;

var newh, max, prev, pmax, cur: lptr;

newh:= nil; { выходной список - пустой }

while head <> nil do { цикл, пока не опустеет входной список }

max:=head;

prev:=head; { нач. максимум - 1-й элемент }

cur:=head^.next; { поиск максимума во входном списке }

while cur <> nil do

if cur^.key > max^.key then

{ запоминается адрес максимума и адрес предыдущего элемента }

max:=cur;

pmax:=prev;

end;

prev:=cur;

cur:=cur^.next; { движение по списку }

end;

{ исключение максимума из входного списка }

if max = head then

head:=head^.next else

pmax^.next:=max^.next;

{ вставка в начало выходного списка }

max^.next:=newh;

newh:=max;

end;

Result:=newh;

end;

Следует обратить внимание на несколько особенностей алгоритма. Во-первых, во входном списке ищется всякий раз не минимальный, а максимальный элемент. Поскольку элемент включается в начало выходного списка, элементы с большими ключами оттесняются к концу выходного списка и последний, таким образом, оказывается отсортированным по возрастанию ключей.

Во-вторых, при поиске во входном списке сохраняется не только адрес найденного элемента в списке, но и адрес предшествующего ему в списке элемента – это впоследствии облегчает исключение элемента из списка.

В-третьих, обратите внимание на то, что не возникает проблем с пропуском во входном списке тех элементов, которые уже выбраны – они просто исключены из входной структуры данных.

В следующем примере представлена реализация сортировки вставками. Из входного списка выбирается (и исключается) первый элемент и вставляется в выходной список «на свое место» в соответствии со значениями ключей. Сортировка включением на векторной структуре требовала большого числа перемещений элементов в памяти. Обратите внимание, в обоих примерах пересылок данных не происходит, все элементы остаются на своих местах в памяти, меняются только связи между ними – указатели.

data = Integer;

{ Сортировка вставками на 1-связном списке }

function Sort(head: lptr): lptr;

var newh, cur, sel: lptr;

newh:= nil; { выходной список - пустой }

while head <> nil do

begin { цикл, пока не опустеет входной список }

sel:=head; { элемент, который переносится в выходной список }

head:=head^.next; { продвижение во входном списке }

{ выходной список пустой или элемент меньше 1-го - вставка в начало }

if (newh = nil) or (sel^.key < newh^.key) then

sel^.next:=newh;

newh:=sel;

end;

{ вставка в середину или в конец }

Дата добавления: 2014-01-07