Применение линейных списков
Begin
Begin
Begin
Begin
Begin
Begin
Begin
Begin
Begin
Begin
Begin
{ новый элемент указывает на бывший первый элемент списка;
если head = nil, то новый элемент будет и последним элементом списка }
cur^.next:=head;
{ новый элемент становится первым в списке,
указатель на начало теперь указывает на него }
head:=cur;
end;
end;
Удаление элемента из списка. Удаление элемента из односвязного списка показано на рис. 6.7. Процедуру удаления легко выполнить, если известен адрес элемента, предшествующего удаляемому (prev на рис. 6.7. а). Однако на рис. 6.7 и в примере приводится процедура для случая, когда удаляемый элемент задается своим адресом del.
 |
а).
 |
б).
Рис. 6.7. Удаление элемента из 1-связного списка из середины списка (а) и из начала (б).
Процедура обеспечивает удаление из середины и из начала списка.
{ Удаление элемента из любого места 1-связного списка }
procedure DeleteSll(
var head: sllptr; { указатель на начало списка, может измениться в процедуре }
del: sllptr); { указатель на элемент, который удаляется }
var prev: sllptr; { адрес предыдущего элемента }
{ попытка удаления из пустого списка расценивается как ошибка
(в последующих примерах этот случай учитываться не будет) }
if head = nil then
Writeln('Ошибка!');
Halt;
end;
{ если удаляемый элемент - первый в списке,
то следующий за ним становится первым }
if del = head then
head:=del^.next else
{ удаление из середины списка }
{ приходится искать элемент, предшествующий удаляемому; поиск производится перебором списка с самого его начала, пока не будет найдет элемент, поле next которого совпадает с адресом удаляемого элемента }
prev:=head^.next;
while (prev^.next <> del) and (prev^.next <> nil) do
prev:=prev^.next;
if prev^.next = nil then
{ это случай, когда перебран весь список, но элемент не найден,
он отсутствует в списке; расценивается как ошибка }
Writeln('Ошибка!');
Halt;
end;
{ предыдущий элемент теперь указывает на следующий за удаляемым }
prev^.next:=del^.next;
end;
{ элемент исключен из списка, теперь можно освободить занимаемую им память }
Dispose(del);
end;
Удаление элемента из двухсвязного списка требует коррекции большего числа указателей, как показано на рис. 6.8. Процедура удаления, чем для односвязного списка, так как в ней не нужен поиск предыдущего элемента (выбирается по указателю назад).
Рис. 6.8. Удаление элемента из 2-связного списка.
Перестановка элементов списка. Изменчивость динамических структур предполагает не только изменения размера структуры, но и изменения связей между элементами. В качестве примера приведем перестановку двух соседних элементов списка (рис. 6.9). В алгоритме предполагается известным адрес элемента, предшествующего паре, в которой производится перестановка. В алгоритме также не учитывается случай перестановки первого и второго элементов.
Рис. 6.9. Перестановка соседних элементов 1-связного списка.
{ Перестановка двух соседних элементов в 1-связном списке }
procedure ExchangeSll(
prev: sllptr { указатель на элемент, предшествующий переставляемой паре });
var p1, p2: sllptr); { указатели на элементы пары }
p1:=prev^.next; { указатель на 1-й элемент пары }
p2:=p1^.next; { указатель на 2-й элемент пары }
p1^.next:=p2^.next; { 1-й элемент пары указывает на следующий за парой }
p2^.next:=p1; { 1-й элемент пары теперь следует за 2-ым }
prev^.next:=p2; { 2-й элемент пары теперь становится 1-ым }
end;
В процедуре перестановки для двухсвязного списка нетрудно учесть и перестановку в начале и конце списка (рис. 6.10).
Рис. 6.10. Перестановка соседних элементов 2-связного списка.
Копирование части списка. При копировании исходный список сохраняется в памяти, и создается новый список. Информационные поля элементов нового списка содержат те же данные, что и в элементах старого списка, но поля связок в новом списке совершенно другие, поскольку элементы нового списка расположены по другим адресам в памяти. Существенно, что операция копирования предполагает дублирование данных в памяти.
{ Копирование части 1-связного списка; head - указатель на начало копируемой
части; num - число элементов. Функция возвращает указатель на список-копию }
function CopySll(head: sllptr; num: integer): sllptr;
var cur, head2, cur2, prev2: sllptr;
{ исходный список пуст - копия пуста }
if head = nil then
CopySll:=nil else
cur:=head;
prev2:=nil;
{ перебор исходного списка до конца или по счетчику num }
while (num > 0) and (cur <> nil) do
{ выделение памяти для элемента выходного списка и
запись в него информационной части }
New(cur2);
cur2^.inf:=cur^.inf;
{ если 1-й эл-т выходного списка - запоминается указатель на
начало, иначе - записывается указатель в предыдущий элемент }
if prev2 <> nil then
prev2^.next:=cur2 else head2:=cur2;
prev2:=cur2; { текущий элемент становится предыдущим }
cur:=cur^.next; { продвижение по исходному списку }
num:=num-1; { подсчет элементов }
end;
cur2^.next:=nil; { пустой указатель - в последний элемент выходного списка }
CopySll:=head2; { вернуть указатель на начало выходного списка }
end;
end;
Слияние двух списков. Операция слияния заключается в формировании из двух списков одного и аналогична операции сцепления строк. В случае односвязного списка слияние выполняется просто. Последний элемент первого списка содержит пустой указатель на следующий элемент, этот указатель служит признаком конца списка. Вместо пустого указателя в последний элемент первого списка заносится указатель на начало второго списка. Таким образом, второй список становится продолжением первого.
{ Слияние двух списков. head1 и head2 - указатели на начала
списков. На результирующий список указывает head1 }
procedure UniteSll(var head1, head2: sllptr);
var cur: sllptr;
begin { если 2-й список пустой - нечего делать }
if head2 <> nil then
{ если 1-й список пустой, выходным списком будет 2-й }
if head1 = nil then
head1:=head2 else
{ перебор 1-го списка до последнего его элемента }
cur:=head1;
while cur^.next <> nil do
cur:=cur^.next;
{ последний элемент 1-го списка указывает на начало 2-го }
cur^.next:=head2;
end;
head2:=nil; { 2-й список аннулируется }
end;
end;
Линейные списки находят широкое применение, когда непредсказуемы требования на размер памяти, необходимой для хранения данных, большое число сложных операций над данными, особенно включений и исключений. На базе линейных списков могут строиться стеки, очереди и деки. Представление очереди с помощью линейного списка позволяет достаточно просто обеспечить желаемые механизмы обслуживания очереди.
Линейные связные списки используются также для представления таблиц в случаях, когда размер таблицы может существенно изменяться в процессе работы с ней. Однако доступ к элементам связного линейного списка может быть только последовательным, что не позволяет применить к такой таблице эффективный двоичный поиск и это существенно ограничивает их применимость.
Поскольку упорядоченность такой таблицы не может помочь в организации поиска, задачи сортировки таблиц, представленных линейными связными списками, возникают значительно реже, чем для таблиц в векторном представлении. Однако, в некоторых случаях для таблицы, хотя и не требуется частое выполнение поиска, но задача генерации отчетов требует расположения записей таблицы в некотором порядке.
Некоторые алгоритмы, возможно, потребуют каких-либо усложнений структуры, например, быструю сортировку Хоара целесообразно проводить только на двухсвязном списке; в цифровой сортировке удобно создавать промежуточные списки для цифровых групп и т.д.
Приведем примеры сортировки элементов односвязного линейного списка. Будем полагать, что определен следующий тип данных: