Одномерные двунаправленные списки

Каждый элемент списка содержит два адресных поля Pred и Next. Поле Predсодержит адрес предыдущего элемента списка (в первом элементе это поле равно 0). Поле Next содержит адрес следующего элемента списка (в последнем элементе это поле равно 0). Такая организация списка позволяет перемещаться по его элементам в двух направлениях.

Тип данных для элементов такого списка можно определить так:

Struct t_Item

{

Double Inf;

t_Item * Pred,

* Next;

};

Здесь предполагается, что информационное поле имеет тип double.

Для создания такого списка можно использовать следующую функцию:

t_Item *CreateList ( unsigned Length )

{

t_Item *Curr = 0,// Адрес очередного элемента списка

*Next = 0;// Адрес следующего за очередным элемента списка

// Начинаем создавать список с последнего элемента

for ( unsigned i = 1; i <= Length; ++ i )

{

// Создаем очередной элемент списка

Curr = new t_Item;

// В адресную часть записываем адрес следующего

// за очередным элемента списка

Curr->Next = Next;

if ( Next )// Следующий элемент существует (Next не равен 0)

// Очередной элемент с адресом Curr является предыдущим

// элементом для элемента с адресом Next

Next->Pred = Curr;

// Запоминаем адрес очередного элемента в качестве

// следующего элемента для следующего шага цикла

Next = Curr;

}

// Для первого элемента списка адрес предыдущего элемента

// должен быть равен 0

Curr->Pred = 0;

// Возвращаем адрес последнего созданного элемента,

// как адрес первого элемента списка

Return Curr;

}

Функции удаления списка DeleteList,доступа кэлементам списка ListItem,определения длины спискаLengthList и перемещения элемента MoveItem остаются такими же, как и для однонаправленного списка (необходимо только заменить идентификатор поля Adr на Next). Остальные функции требуют небольшой коррекции, связанной с дополнительной обработкой адресного поля Pred:

t_Item *InsItem( t_Item * &Beg, unsigned Index )

{

t_Item * Item = new t_Item;

if ( !Index || !Beg)

{

Beg->Pred = Item;

Item->Pred = 0;

Item->Next = Beg;

Beg = Item;

Return Item;

}

t_Item * PredItem = Beg;

-- Index;

while ( PredItem->Next && ( Index -- ) )

PredItem = PredItem->Next;

Item->Pred = PredItem;

Item->Next->Pred = Item;

Item->Next = PredItem->Next;

PredItem->Next = Item;

Return Item;

}

void DelItem( t_Item * &Beg, unsigned Index )

{

if ( Index >= LengthList ( Beg ) )

Return;

t_Item * Item;

if ( !Index )

{

Item = Beg->Next;

Delete Beg;

Beg = Item;

Beg->Pred = 0;

Return;

}

Item = ListItem ( Beg, Index - 1, 0 );

t_Item * DItem = Item->Next;

Item->Next = DItem->Next;

Item->Next->Pred = Item;

Delete DItem;

}

Многомерные списки

Стек