Усложненные списковые структуры
20 Август 2010, 19:15
Двунаправленные линейные списки
Недостатком рассмотренных выше списковых структур является их однонаправленность от первого элемента к последнему. Если при обработке списков часто бывает необходимо переходить от текущего элемента к его предшественнику, то такая односторонняя организация становится неудобной. Выходом является построение двунаправленных списков, в которых каждый элемент “знает” обоих своих соседей, как левого, так и правого.
Для этого каждый элемент должен иметь не одно, а два связующих поля: указатель на элемент слева и указатель на элемент справа.
Аналогично обычным спискам, удобно ввести фиктивный заголовочный элемент, а поскольку двунаправленные списки являются симметричными, удобно сделать их замкнутыми, кольцевыми: правая ссылка последнего элемента указывает на заголовок, а левая ссылка заголовка – на последний элемент. Адрес заголовка определяется указателем Head.
Отметим достоинства и недостатки двунаправленных списков. Достоинство – простота перехода от текущего элемента к любому его соседу. Недостатки – увеличиваются затраты памяти и число операций на поддержку дополнительного указателя.
Двунаправленный список можно реализовать как на основе массива (причем – обеими способами), так и динамически.
В последнем случае описание структуры данных выглядит следующим образом:
struct List2Item {
int Info;
List2Item *Right;
List2Item *Left;
};
Если Head есть указатель на заголовок, то пустой список создается так:
- выделяется память под заголовок, адресуемая указателем Head
- оба ссылочных поля заголовка устанавливаются в адрес самого заголовка:
Head->Right = Head;
Head->Left = Head;
(при этом пустая ссылка NULL нигде НЕ используется!)
Набор операций расширяется просмотром и поиском не только в прямом, но и в обратном направлениях. Немного изменяется условие достижения конца списка – вместо условия появления пустой ссылки надо использовать условие получения на текущем шаге адреса заголовка. Например, проход в обратном направлении реализуется так:
- устанавливаем начальное значение указателя текущего элемента на последний элемент списка:
Current = Head->Left;
- организуем цикл прохода до достижения заголовка
while (Current != Head)
Current = Current->Left;
Удаление заданного элемента требует изменения большего числа ссылочных полей. Надо изменить правый указатель у левого соседа удаляемого элемента и левый указатель у правого соседа.
Если удаляемый элемент адресуется указателем Current, то Current->Left определяет адрес левого соседа, а pCurrent->Right – адрес правого соседа. Тогда необходимые изменения реализуются так:
Current->Left->Right = Current->Right;
Current->Right->Left = Current->Left;
Аналогично выполняется добавление нового элемента, например – после заданного указателем Current. Пусть как обычно новый элемент определяется указателем Tmp. Тогда для вставки его в список надо настроить оба его ссылочных поля, изменить правое ссылочное поле у текущего элемента и левое ссылочное поле у его правого соседа.
Необходимые присваивания (порядок следования важен!):
Tmp->Right = Current->Right;
Tmp->Left = Current;
Current->Right->Left = Tmp;
Current->Right = Tmp;
Аналогично реализуется добавление нового элемента перед заданным элементом, только вместо правого соседа обрабатывается левый сосед текущего элемента.
Комбинированные структуры данных: массивы и списки списков
Здесь каждый элемент массива или основного списка является началом вспомогательного списка, причем эти вспомогательные списки могут содержать разное число элементов (одного типа).
В обоих случаях в первую очередь вводится тип данных, описывающий структуру элементов вспомогательного списка:
struct SubList {
<описание информационных полей>;
SubList *Next;
};
После этого описывается либо основной массив указателей, либо структура элементов основного списка:
SubList MainArray[N];
strcut MainList {
MainList *NextMain;
SubList *HeadSub;
};
Обработка таких структур включает больше операций, поскольку практически любая типовая операция (поиск, просмотр, добавление, удаление) может выполняться как с основным массивом или списком, так и с любым вспомогательным списком. Например, полный поиск или полный проход реализуется двойным циклом: внешний цикл проходит по элементам основного списка, а внутренний обрабатывает отдельно каждый вспомогательный список. Для этого необходимы две ссылочные переменные: CurrentMain для прохода по основному списку и CurrentSub – для прохода по вспомогательному списку.
CurrentMain = “адрес первого элемента основного списка”;
while(CurrentMain != NULL)
{
CurrentSub = CurrentMain->HeadSub;
while(CurrentSub != NULL)
CurrentSub = CurrentSub->Next;
}
CurrentMain = CurrentMain->NextMain;
Добавление и удаление элементов во вспомогательных списках выполняется обычным образом. Небольшие особенности имеет удаление элемента из основного списка, поскольку в этом случае как правило надо удалить и весь вспомогательный список. Поэтому прежде всего организуется проход по вспомогательному списку с удалением каждого элемента, а потом уже производится удаление элемента основного списка.
Иногда удобно в элементах основного списка хранить не только адрес первого элемента вспомогательного списка, но и адрес последнего элемента. При необходимости как основной, так и вспомогательные списки могут быть двунаправленными.
Кроме того, поскольку стеки и очереди можно рассматривать как частные случаи списков, легко можно реализовать такие структуры как массив или список стеков, массив или список очередей и т.д.
