3. 6.2.3. Применение линейных списков

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

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

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

Некоторые алгоритмы, возможно, потребуют каких-либо усложнений структуры, например, быструю сортировку Хоара целесообразно проводить только на двухсвязном списке; в цифровой сортировке удобно создавать промежуточные списки для цифровых групп и т.д.

Приведем примеры сортировки элементов односвязного линейного списка. Будем полагать, что определен следующий тип данных:

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;

begin

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

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

begin

max:=head;

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

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

while cur <> nil do

begin

if cur^.key > max^.key then

begin

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

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;

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

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

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

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

type

data = Integer;

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

function Sort(head: lptr): lptr;

var newh, cur, sel: lptr;

begin

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

while head <> nil do

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

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

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

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

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

begin

sel^.next:=newh;

newh:=sel;

end;

end else

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

begin

cur:=newh;

{ до конца выходного списка или пока ключ

следующего элемента не будет больше вставляемого }

while (cur^.next <> nil) and (cur^.next^.key < sel^.key) do

cur:=cur^.next;

{ вставка в выходной список после элемента cur }

sel^.next:=cur^.next;

cur^.next:=sel;

end;

Result:=newh;

end;