Файл: Курсач.docx

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

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

Машинное представление связных линейных списков

На рисунке приведена структура односвязного списка. На нем поле INF - информационное поле, данные, NEXT - указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка.

Структура односвязного списка

Однако, обработка односвязного списка не всегда удобна, так как отсутствует возможность продвижения в противоположную сторону. Такую возможность обеспечивает двухсвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. Структура линейного двухсвязного списка приведена на рисунке где поле NEXT - указатель на следующий элемент, поле PREV - указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать nil, как и показано на рисунке.

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

Структура двухсвязного списка

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

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

Структура кольцевого двухсвязного списка

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

Реализация операций над связными линейными списками

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

В программных примерах подразумеваются определенными следующие типы данных:

любая структура информационной части списка: type data = ...;
элемент односвязного списка (sll - single linked list):
type
sllptr = ^slltype; { указатель в односвязном списке }
slltype = record { элемент односвязного списка }
inf : data; { информационная часть }
next : sllptr; { указатель на следующий элемент }

end;

элемент двухсвязного списка (dll - double linked list):
type
dllptr = ^dlltype; { указатель в двухсвязном списке }
dlltype = record { элемент односвязного списка }
inf : data; { информационная часть }
next : sllptr; { указатель на следующий элемент (вперед) }
prev : sllptr; { указатель на предыдущий элемент (назад) }

end;

Перебор элементов списка.

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

Алгоритм перебора для односвязного списка представляется программным примером

{==== Программный пример ====}

{ Перебор 1-связного списка }

Procedure LookSll(head : sllptr);

{ head - указатель на начало списка }

var cur : sllptr; { адрес текущего элемента }

begin

cur:=head; { 1-й элемент списка назначается текущим }

while cur <> nil do begin

< обработка c^.inf >

{обрабатывается информационная часть того эл-та,

на который указывает cur.

Обработка может состоять в:

печати содержимого инф.части;
модификации полей инф.части;
сравнения полей инф.части с образцом при поиске по ключу;
подсчете итераций цикла при поиске по номеру;

cur:=cur^.next;

{ из текущего эл-та выбирается указатель на следующий эл-т и для следующей итерации следующий эл-т становится текущим; если текущий эл-т был последний, то его поле next содержит пустой указатель и, т.обр. в cur запишется nil, что приведет к выходу из цикла при проверке условия while } end; end;

В двухсвязном списке возможен перебор как в прямом направлении (он выглядит точно так же, как и перебор в односвязном списке), так и в обратном. В последнем случае параметром процедуры должен быть tail - указатель на конец списка, и переход к следующему элементу должен осуществляться по указателю назад:

cur:=cur^.prev;

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

Вставка элемента в список.

Вставка элемента в середину односвязного списка показана на рисунке .

Вставка элемента в середину 1-связного списка

{==== Программный пример ====}

{ Вставка элемента в середину 1-связного списка }

Procedure InsertSll(prev : sllptr; inf : data);

{ prev - адрес предыдущего эл-та; inf - данные нового эл-та }

var cur : sllptr; { адрес нового эл-та }

begin

{ выделение памяти для нового эл-та и запись в его инф.часть }

New(cur); cur^.inf:=inf;

cur^.next:=prev^.next; { эл-т, следовавший за предыдущим теперь

будет следовать за новым }

prev^.next:=cur; { новый эл-т следует за предыдущим }

end;

Рисунок представляет вставку в двухсвязный список.

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

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

{==== Программный пример ====}

{ Вставка элемента в любое место 1-связного списка }

Procedure InsertSll

var head : sllptr; { указатель на начало списка, может измениться в

процедуре, если head=nil - список пустой }

prev : sllptr; { указатель на эл-т, после к-рого делается вставка,

если prev-nil - вставка перед 1-ым эл-том }

inf : data { - данные нового эл-та }

var cur : sllptr; { адрес нового эл-та }

begin

{ выделение памяти для нового эл-та и запись в его инф.часть }

New(cur); cur^.inf:=inf;

if prev <> nil then begin { если есть предыдущий эл-т - вставка в

середину списка, см. прим.5.2 }

cur^.next:=prev^.next; prev^.next:=cur;

end

else begin { вставка в начало списка }

cur^.next:=head; { новый эл-т указывает на бывший 1-й эл-т списка;

если head=nil, то новый эл-т будет и последним эл-том списка }

head:=cur; { новый эл-т становится 1-ым в списке, указатель на

начало теперь указывает на него }

end; end;

Удаление элемента из списка.

Удаление элемента из односвязного списка показано на рисунке

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

{==== Программный пример ====}

{ Удаление элемента из любого места 1-связного списка }

Procedure DeleteSll(

var head : sllptr; { указатель на начало списка, может

измениться в процедуре }

del : sllptr { указатель на эл-т, к-рый удаляется } );

var prev : sllptr; { адрес предыдущего эл-та }

begin

if head=nil then begin { попытка удаления из пустого списка

асценивается как ошибка (в последующих примерах этот случай

учитываться на будет) }

Writeln('Ошибка!'); Halt;

end;

if del=head then { если удаляемый эл-т - 1-й в списке, то

следующий за ним становится первым }

head:=del^.next

else begin { удаление из середины списка }

{ приходится искать эл-т, предшествующий удаляемому; поиск производится перебором списка с самого его начала, пока не будет найдет эл-т, поле next к-рого совпадает с адресом удаляемого элемента }

prev:=head^.next;

while (prev^.next<>del) and (prev^.next<>nil) do

prev:=prev^.next;

if prev^.next=nil then begin

{ это случай, когда перебран весь список, но эл-т не найден, он отсутствует в списке; расценивается как ошибка (в последующих примерах этот случай учитываться на будет) }

Writeln('Ошибка!'); Halt;

end;

prev^.next:=del^.next; { предыдущий эл-т теперь указывает

на следующий за удаляемым }

end;

{ элемент исключен из списка, теперь можно освободить

занимаемую им память }

Dispose(del);

end;

Удаление элемента из двухсвязного списка требует коррекции большего числа указателей, как показано на рисунке.

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