Типичным примером незвязного (физически) списка является массив. В этой главе мы рассмотрим те самые "специальные динамические структуры данных", которые и получили название свЯзных списков.
Связные списки свободны от этих ограничений. Они допускают гибкие методы доступа; извлечение (чтение) элемента из списка не приводит к удалению его из списка и потере данных. Для фактического удаления элемента из связного списка требуется специальная процедура.
Рассмотрим основные из этих операций для каждого вида списка отдельно, вместе с особенностями этих видов списков.
Линейный односвязный список
Линейный односвязный список является самым простым видом связных списков. Такой список можно определить с помощью описаний типов (см. пример 1).
Процедуры работы с линейным односвязным списком на языке Паскаль
Type
rel1 = ^elem; (* Указатель на запись *)
elem = record
next: rel1;
data: <Тип хранимых данных> (* Любой допустимый тип данных *)
end;
var
L1: rel1;
Ддя того, чтобы такие операции, как добавление или удаление звена, выполнялись одинаково, независимо от места их выполнения в списке, удобно использовать ведущее или заглавное звено - самое первое звено списка, в котором не обязаны храниться полезные данные. Его создание для односвязного списка можно осуществить следующим образом:
var a, L1: list1;
begin
...
new(L1);
L1^.next := nil;
a := L1;
...
Указатель на начало списка L1, значением которого является адрес ведущего звена, представляет список как единый программный объект.
Указатель на следующий элемент в последнем звене списка имеет значение nil (NULL или просто 0 в Си/Си++), что является признаком линейного списка.
procedure insert1(link: rel1; info: <Тип>);
var q: rel1;
begin
new(q);
q^.data := info;
q^.next := link^.next;
link^.next := q
end;
procedure delete1(link:rel1);
var q: rel1;
begin
if link^.next <> nil then
begin
q := link^.next;
link^.next := link^.next^.next;
dispose(q);
end
end;
function search1(l: rel1; info: <Тип>; var r: rel1):boolean;
var q: rel1;
begin
search1 := false;
r := nil;
q := l^.next;
while (q <> nil) and (r <> nil) do
begin
if q^.data = info then
begin
search := true;
r := q
end;
q := q^.next
end
end;
|
Процедуры добавления и удаления звеньев являются критическими с точки зрения сохранения целостности списка. При неправильном выполнении этих процедур (т.е. при неправильной очерёдности выполнения операций присваивания) возможны 2 ошибочные ситуации:
1. Список "рвётся" по месту вставки или удаления звена, и звено, оказавшее последним,
замыкается либо само на себя (чаще всего) (т.е. указатель next или аналогичный ему в этом звене получает значение адреса этого же звена), либо на одно из предшествующих звеньев (в зависимости от неправильной реализации операций вставки или удаления звена). При попытке просмотра списка процедура просмотра зацикливается и бесконечно выводит содержимое одного и того же звена (или нескольких звеньев).
2. Список так же "рвётся" по месту вставки или удаления звена, но указатель в звене, ставшем последним, получает какое-то произвольное значение, которое трактуется как адрес следующего звена (реально не существующего), у которого также есть указатель next, содержащий какой-то адрес, и так далее, до тех пор, пока случайно не попадётся блок данных, для которого указатель next не будер равен нулю. При попытке просмотра списка на дисплей сначала выводятся правильные данные, а затем случайный набор символов.
В обоих случаях к звеньям в "оторвавшейся" части ("хвосте") списка больше нет доступа, и хранящиеся в них данные можно считать потерянными.
Для предовращения возникновения таких ошибок следует соблюдать правильный порядок проведения связей (т.е. присваивания указателей) при вставке нового звена и удалении существующего (очерёдность операций указана):
|
Добавление звена в произвольную позицию за ведущим звеном:
struct Link1
{
int data;
Link1* next;
};
void Insert1(Link1* link, int data) // link - звено, за которым вставляется новое
{
Link1* q = new Link1; // 1 Выделение памяти под новое звено
q->data = data; // 2 Ввод данных
q->next = link->next; // 3 Проведение связи от нового звена к следующему
link->next = q; // 4 Проведение связи от "старого" звена у новому
}
Возможность перемещаться по 1-связному списку только в одном направлении приводит к тому, что при удалении звена приходится задавать не реально удаляемое звено, а предшествующее ему. Это делается для того, чтобы можно было скорректировать связь для предшествующего звена, добраться до которого от удаляемого иначе невозможно.
Удаление звена из любого места списка за ведущим звеном:
void Delete1(Link1* link) // link - звено, предшествующее удаляемому
{
Link1* q;
if (link->next) // Проверка на наличие звена, следующего за link
{
q = link->next // 1 Запоминание удаляемого звена для операции delete
link->next = q->next; // 2 Проведение новой связи в обход удаляемого звена
delete q; // 3 Очистка памяти
}
}
|
Одной из наиболее простых операций со всеми типами списков является их прохождение, т.е. поочерёдное получение доступа ко всем элементам. Приведём
процедуру, реализующую эту операцию для просмотра списка (другие варианты использования прохождения – поиск данных и сохранение списка в файл). В случае перемещения по 2-связному списку в "прямом" направлении эта процедура является одинаковой для 1- и 2-связного линейных списков.
Просмотр 1-связного линейного списка
void Show(Link1* link)
{
Link1 *q = link->next; // Учитывается наличие "пустого" ведущего звена
while (q) // или while(q!=NULL)
{
cout<<q->data<<' '; // или другая операция
q = q->next; // Переход по списку
}
cout<<endl;
}
|
Поиск в списке является вариантом операции просмотра и
отличается тем, что:
1. вместо операции вывода на экран (cout<<q->data) используется операция сравнения
искомых данных с хранящимися в звеньях списка;
2. если искомые данные найдены, нет необходимости перемещаться по списку дальше.
Поиск в односвязных списках имеет следующую особенность. Если он выполняется в сочетании с удалением, то результатом поиска может (или должно)
быть не то звено, в котором содержатся искомые данные, а предшествующее ему. В итоге для поиска в списке могут потребоваться либо две различные процедуры – "обычная" и находящая предыдущее звено, либо одна универсальная, позволяющая
найти оба звена – с искомыми данными и предшествующее ему. Рассмотрим в качестве примера именно этот вариант
Универсальная процедура поиска (находит звено с ключом поиска и предшествующее ему)
int Search(Link1* Start, // Точка начала поиска
Link1*& Find, // Указатель для звена с искомыми данными
Link1*& Pred, // Указатель для предыдущего звена
int Key) // Ключ поиска
{
Link1* Cur = Start->next; // Текущее звено
Pred = Start; // Предыдущее звено ("отстаёт" на 1 шаг от текущего)
int Success = 0; // Признак успеха поиска (установлен в 0)
while (Cur && !Success) // Операция логическое "И"
{
if (Cur->data == Key) // нашли
{
Find = Cur; // Запоминание найденного звена
Success = 1; // Установка в 1 признака успеха
break; // Выход из цикла при удачном поиске
}
Pred = Cur; // Перемещение предыдущего звена
Cur = Cur->next; // Переход по списку вперёд
}
return Success;
}
Следует отметить, что возможны разные (в том числе более короткие) варианты реализации такого алгоритма, например, без переменной Success (вместо неё используется указатель Find, который до начала поиска должен получить значение NULL и сохранить его при неудачном поиске).
Процедура, которая находит только искомое звено, является более простой, – в ней не нужен указатель Pred и все операторы, в которых он используется.
Похожая процедура применяется для 1-связного кольцевого списка.
Отличие её от рассмотренного примера заключается в условии продолжения цикла в операторе while:
while(Cur != Start && !Success) // Для кольцевого списка
|
Ведущее (или заглавное) звено. Все приведённые выше примеры на языке Си++ подразумевают наличие в списке ведущего звена. Создаваться это звено может либо отдельной процедурой, либо следующим набором операторов (эти же операторы и будут находиться в процедуре):
Link1 *L1 = new Link1; // Выделение памяти под звено
L1->next = NULL; // Ведущее звено одновременно является последним
Возможна работа со связным списком и без выделенного ведущего звена, т.е. первое звено является обычным, в нём содержатся полезные данные. Именно такой вид списка использовался для организации стека. Ещё один пример использования подобных списков - очередь.
Занесение в очередь и извлечение из очереди, построенной на основе 2-связного списка
void queue_in(Link2*& q, // "Голова" очереди
Link2*& e, // "Хвост" очереди
int k) // Вводимые данные
{
Link2* n = new node; // Новый узел
n->data = k;
n->next = q;
if (q)
q->prev = n;
else
e = n;
n->prev = 0;
q = n;
}
int queue_out(Link2*& q, Link2*& e)
{
int k = e->data;
Link2* d = e;
e = d->prev;
if (e)
e->next = 0;
else
q = e;
delete d;
return k;
}
Для упрощения обработки "головы" и "хвоста" очереди использован 2-связный список.
|
В остальных случаях (т.е. для обычных списков) использование ведущего звена является предпочтительным, т.к. позволяет избежать проверок при добавлении и удалении звеньев.
Недостатки односвязного списка заключаются в следующем:
1. По такому списку можно перемещаться только от начального звена к конечному. Начинать можно с любого звена в списке, но если вдруг возникнет необходимость обратиться к предшествующим элементам, придется начинать с начального звена, что неудобно, нерационально и усложняет алгоритмы обработки данных.
2. Наличие только одной связи снижает надёжность хранения данных в 1-связном списке.
3. Следствием первого недостатка является усложнение взаимодействия операций поиска и удаления.
Достоинствами этого списка являются меньший расход памяти по сравнению с другими свЯзными динамическими структурами данных (всего 1 указатель) и
простота операций.
Линейный двусвязный список
Этот список свободен от недостатков, присущих односвязному списку. Для этого в каждое звено добавлен еще один указатель на тип звена, значением которого является адрес предыдущего звена списка. Тип звена на языках Си/Си++:
struct Link2
{
int data;
Link2 *next, *prev;
};
Структура списка будет выглядеть следующим образом (значения нулевых указателей показаны для языка Паскаль):
Ведущее звено этого списка создаётся следующим набором операторов:
Link2 *L2 = new Link2;
L2->next = NULL;
L2->prev = NULL;
По операторам создания ведущего звена можно судить о том, является список, 1- или 2-связным, линейным или кольцевым. Нулевые значения указателей next и prev являются признаком линейного списка.
Графически состояние списка после создания ведущего звена может быть отображено следующим образом:
Преимущества двусвязного списка:
- есть возможность перестроить поврежденный список;
- проще выполняются некоторые операции (например, удаление).
Операции с 2-связным списком.Всё, что касалось операций добавления звена и его удаления для 1-связного списка, справедливо и для 2-связного. Так же должен соблюдаться правильный порядок проведения (или удаления) связей между звеньями, но таких операций стало больше, т.к. должны обрабатываться 2 указателя. Кроме того, каждая из операций обладает дополнительыми особенностями:
1. При добавлении нового звена в пустой список, т.е. содержащий только ведущее звено (см. предыдущий рисунок), или при добавлении звена в конец списка (для пустого списка обе эти ситуации совпадают) необходимо проверять наличие звена, которое будет следующим за добавляемым (для пустого списка или конца списка такого звена нет, а значит нет и указателя, обозначающего связь). Такая же проверка должна выполняться при удалении звена.
2. Возможность перемещаться по списку в обоих направлениях позволяет напрямую задавать удаляемое звено (а не ему предшествующее, как в 1-связном списке). Следствием этого является упрощение как операции удаления, так и операции поиска.
Добавление звена в произвольную позицию за ведущим звеном
void Insert2(Link2* St, int data)
{
Link2* q = new Link2; // 1 Выделение памяти под звено
q->data = data; // 2 Ввод данных
q->next = St->next; // 3 Проведение связи от нового звена вперёд
q->prev = St; // 4 Проведение связи от нового звена назад
St->next = q; // 5 Проведение связи от предыдущего звена к новому
if (q->next) // Проверка наличия следующего звена
q->next->prev = q; // 6 Проведение связи от следующего звена к новому
}
Удаление звена из любого места списка за ведущим звеном
void Delete2(Link2* del)
{
del->prev->next = del->next; // 1 Обработка связи вперёд
if (del->next)
del->next->prev = del->prev; // 2 Обработка связи назад
delete del; // 3 Освобождение памяти
}
Поиск в 2-связном списке
int Search2(Link2* Start, Link2*& Find, int Key)
{
Link2* Cur=Start->next;
int Success = 0;
while (Cur && !Success)
{
if (Cur->data == Key)
{
Find = Cur;
Success = 1;
break;
}
Cur = Cur->next;
}
return Success;
}
Эта процедура поиска фактически является (за исключением типа данных Link2 вместо Link1) процедурой "обычного" поиска (т.е. не для удаления) в 1-связном списке.
|
Операция просмотра списка в прямом направлении ничем не отличается от просмотра 1-связного списка.
Кольцевые списки
Если значение указателя последнего звена линейного односвязного списка заменить с nil (или NULL) на адрес ведущего звена, то линейный список превратится в односвязный кольцевой список.
Для двусвязного списка, кроме того, нужно заменить с nil на адрес последнего звена значение второго указателя в ведущем звене. Получится двусвязный кольцевой (циклический) список.
В односвязном кольцевом списке можно переходить от последнего звена к заглавному, а в двусвязном – еще и от заглавного к последнему.
Двусвязный кольцевой список выглядит так:
Кольцевой список, как и линейный, идентифицируется как единый программный объект указателем, например L2, значением которого является адрес заглавного звена.
Возможен другой вариант организации кольцевого списка:
Оба варианта сопоставимы по сложности. Для первого варианта проще выполняется вставка нового элемента как в начало списка (после заглавного звена), так и в конец – так как вставка звена в конец кольцевого списка эквивалентна вставке перед заглавным звеном, но каждый раз при циклической обработке списка нужно проверять, не является ли текущее звено заглавным (или не совпадает ли текущее звено с точкой начала обработки).
Рассмотрим операции с кольцевыми списками.
Отсутствие "последнего" звена приводит к ещё большему упрощению операций добавления и удаления, по сравнению с 1- и 2-связным линейным списком. Например, для 1-связного кольцевого списка в процедуре удаления отсутствует оператор if – проверка на существование звена, следующего за заданным (в кольцевом списке такое звено всегда есть). Такие же операторы отсутствуют в процедурах добавления и удаления звеньев для 2-связного кольцевого списка.
При циклической обработке кольцевого списка нужно учесть, что формально последнего звена нет.
Программа работы с двусвязным кольцевым списком на языке Паскаль
Type
rel2 = ^elem2;
elem2 = record
next: rel1;
prev: rel2;
data: <Тип хранимых данных>
end;
list2 = rel2;
procedure insert2(pred: rel2; info: <Тип>);
var
q: rel2;
begin
new(q); (* Создание нового звена *)
q^.data := info;
q^.next := pred^.next;
q^.prev := pred^.next^.prev;
pred^.next.prev := q;
pred^.next := q
end;
При вставке в начало списка (после заглавного звена) нужно указать в качестве аргумента pred адрес заглавного звена, то есть указатель на список L2.
procedure delete2(del: rel2);
begin
del^.next^.prev := del^.prev;
del^.prev^.next := del^.next;
dispose(del);
end;
function search2(list: rel2; info: <Тип>; var point: rel2):boolean;
var
p,q: rel2;
b:boolean;
begin
b := false;
point := nil;
p := list;
q := p^.next;
while (p <> q) and (not b) do
begin
if q^.data = info then
begin
b := true;
point := q
end;
q := q^.next
end;
search2 := b
end;
...
...
var
l2: list2;
r: rel2;
begin (* Создание заглавного звена *)
new(r);
r^.next := r;
r^.pred := r;
l2 := r;
...
...
end.
Процедуры работы с двусвязным кольцевым списком на языке Си++
Тип данных для кольцевого 2-связного списка такой же, как и для 2-связного линейного. То же самое справедливо для 1-связных списков. По типу звена списка нельзя судить о его архитектуре, можно - только о числе связей.
Добавление звена в произвольную позицию за ведущим звеном
void Insert(Link2* Pred, int data)
{
Link2* Loc = new Link2; // 1
Loc->Value = data; // 2
Loc->next = Pred->next; // 3
Loc->prev = Pred; // 4
Pred->next = Loc; // 5
Loc->next->prev = Loc; // 6
}
Удаление звена из любого места списка за ведущим звеном
void Delete2(Link2* Del)
{
Del->prev->next = Del->next; // 1
Del->next->prev = Del->prev; // 2
delete Del; // 3
}
Поиск
int Search(Link2* Start, Link2*& Find, int Key)
{
Link2* Cur = Start->next;
int Success = 0;
while (Cur != Start && !Success)
{
if (Cur->Value == Key)
{
Find = Cur;
Success = 1;
break;
}
Cur = Cur->next;
}
return Success;
}
Прекращение поиска в случае неудачи происходит при достижении "текущим" указателем Cur точки начала поиска Start, т.е. при невыполнении условия в операторе while:
while(Cur != Start ... )
|
Ведущее звено кольцевого 2-связного списка создаётся набором операторов:
Link2 *L2 = new Link2;
L2->next = L2;
L2->prev = L2;
Графически состояние списка после создания этого звена может быть представлено таким образом:
