Применение линейных списков
Линейные списки находят широкое применение в приложениях, где непредсказуемы требования на размер памяти, необходимой для хранения данных; большое число сложных операций над данными, особенно включений и исключений. На базе линейных списков могут строится стеки, очереди и деки. Представление очереди с помощью линейного списка позволяет достаточно просто обеспечить любые желаемые дисциплины обслуживания очереди. Особенно это удобно, когда число элементов в очереди трудно предсказуемо.
В программном примере 5 показана организация стека на односвязном линейном списке. Стек представляется как линейный список, в котором включение элементов всегда производятся в начала списка, а исключение - также из начала. Для представления его нам достаточно иметь один указатель - top, который всегда указывает на последний записанный в стек элемент. В исходном состоянии (при пустом стеке) указатель top - пустой. Процедуры StackPush и StackPop сводятся к включению и исключению элемента в начало списка.
Обратите внимание, что при включении элемента для него выделяется память, а при исключении - освобождается. Перед включением элемента проверяется доступный объем памяти, и если он не позволяет выделить память для нового элемента, стек считается заполненным. При очистке стека последовательно просматривается весь список и уничтожаются его элементы. При списковом представлении стека оказывается непросто определить размер стека. Эта операция могла бы потребовать перебора всего списка с подсчета числа элементов. Чтобы избежать последовательного перебора всего списка мы ввели дополнительную переменную stsize, которая отражает текущее число элементов в стеке и корректируется при каждом включении/исключении.
{==== Программный пример 5 ====}
{ Стек на 1-связном линейном списке }
unit Stack;
Interface
type data = ...; { эл-ты могут иметь любой тип }
Procedure StackInit;
Procedure StackClr;
Function StackPush(a : data) : boolean;
Function StackPop(Var a : data) : boolean;
Function StackSize : integer;
Implementation
type stptr = ^stit; { указатель на эл-т списка }
stit = record { элемент списка }
inf : data; { данные }
next: stptr; { указатель на следующий эл-т }
end;
Var top : stptr; { указатель на вершину стека }
stsize : longint; { размер стека }
{** инициализация - список пустой }
Procedure StackInit;
begin top:=nil; stsize:=0; end; { StackInit }
{** очистка - освобождение всей памяти }
Procedure StackClr;
var x : stptr;
begin { перебор эл-тов до конца списка и их уничтожение }
while top<>nil do
begin x:=top; top:=top^.next; Dispose(x); end;
stsize:=0;
end; { StackClr }
Function StackPush(a: data) : boolean; { занесение в стек }
var x : stptr;
begin { если нет больше свободной памяти - отказ }
if MaxAvail < SizeOf(stit) then StackPush:=false
else { выделение памяти для эл-та и заполнение инф.части }
begin New(x); x^.inf:=a;
{ новый эл-т помещается в голову списка }
x^.next:=top; top:=x;
stsize:=stsize+1; { коррекция размера }
StackPush:=true;
end;
end; { StackPush }
Function StackPop(var a: data) : boolean; { выборка из стека }
var x : stptr;
begin
{ список пуст - стек пуст }
if top=nil then StackPop:=false
else begin
a:=top^.inf; { выборка информации из 1-го эл-та списка }
{ 1-й эл-т исключается из списка, освобождается память }
x:=top; top:=top^.next; Dispose(top);
stsize:=stsize-1; { коррекция размера }
StackPop:=true;
end; end; { StackPop }
Function StackSize : integer; { определение размера стека }
begin StackSize:=stsize; end; { StackSize }
END.
Программный пример для организация на односвязном линейном списке очереди FIFO разработайте самостоятельно. Для линейного списка, представляющего очередь, необходимо будет сохранять: top - на первый элемент списка, и bottom - на последний элемент.
Линейные связные списки иногда используются также для представления таблиц - в тех случаях, когда размер таблицы может существенно изменяться в процессе ее существования. Однако, то обстоятельство, что доступ к элементам связного линейного списка может быть только последовательным, не позволяет применить к такой таблице эффективный двоичный поиск, что существенно ограничивает их применимость. Поскольку упорядоченность такой таблицы не может помочь в организации поиска, задачи сортировки таблиц, представленных линейными связными списками, возникают значительно реже, чем для таблиц в векторном представлении. Однако, в некоторых случаях для таблицы, хотя и не требуется частое выполнение поиска, но задача генерации отчетов требует расположения записей таблицы в некотором порядке. Некоторые алгоритмы, возможно, потребуют каких-либо усложнений структуры, например, быструю сортировку Хоара целесообразно проводить только на двухсвязном списке, в цифровой сортировке удобно создавать промежуточные списке для цифровых групп и т.д. Мы приведем два простейших примера сортировки односвязного линейного списка. В обоих случаях мы предполагаем, что определены типы данных:
type lptr = ^item; { указатель на элемент списка }
item = record { элемент списка }
key : integer; { ключ }
inf : data; { данные }
next: lptr; { указатель на элемент списка }
end;
В обоих случаях сортировка ведется по возрастанию ключей. В обоих случаях параметром функции сортировки является указатель на начало неотсортированного списка, функция возвращает указатель на начало отсортированного списка. Прежний, несортированный список перестает существовать.
Пример 6 демонстрирует сортировку выборкой. Указатель newh является указателем на начало выходного списка, исходно - пустого. Во входном списке ищется максимальный элемент. Найденный элемент исключается из входного списка и включается в начало выходного списка. Работа алгоритма заканчивается, когда входной список станет пустым. Обратим внимание читателя на несколько особенностей алгоритма. Во-первых, во входном списке ищется всякий раз не минимальный, а максимальный элемент. Поскольку элемент включается в начало выходного списка, элементы с большими ключами оттесняются к концу выходного списка и последний, таким образом, оказывается отсортированным по возрастанию ключей. Во-вторых, при поиске во входном списке сохраняется не только адрес найденного элемента в списке, но и адрес предшествующего ему в списке элемента - это впоследствии облегчает исключение элемента из списка (вспомните пример 1). В-третьих, обратите внимание на то, что у нас не возникает никаких проблем с пропуском во входном списке тех элементов, которые уже выбраны - они просто исключены из входной структуры данных.
{==== Программный пример 6 ====}
{ Сортировка выборкой на 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; Sort:=newh;
end;
В программном примере 7 - иллюстрации сортировки вставками - из входного списка выбирается (и исключается) первый элемент и вставляется в выходной список "на свое место" в соответствии со значениями ключей. Обратите внимание на то, что в двух последних примерах пересылок данных не происходит, все записи таблиц остаются на своих местах в памяти, меняются только связи между ними - указатели.
{==== Программный пример 7 ====}
{ Сортировка вставками на 1-связном списке }
type data = integer;
Function Sort(head : lptr) : lptr;
var newh, cur, sel : lptr;
begin
newh:=nil; { выходной список - пустой }
while head <> nil do begin { цикл, пока не опустеет входной список }
sel:=head; { эл-т, который переносится в выходной список }
head:=head^.next; { продвижение во входном списке }
if (newh=nil) or (sel^.key < newh^.key) then begin
{выходной список пустой или элемент меньше 1-го-вставка в начало}
sel^.next:=newh; newh:=sel; 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; end; Sort:=newh;
end;
1 2 3 4 5
8 8 8
| |
*
Обратная связь