Struct t_Item

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

Pred = 0 Inf Next = 200

Pred = 100 Inf Next = 300

Pred = 600 Inf Next = 0

…

Beg = 100

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

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

{

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;

}