Вставка элемента в двунаправленный список

Печать (просмотр) двунаправленного списка

Создание двунаправленного списка

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

//создание двунаправленного списка (добавления в конец)

void Make_Double_List(int n,Double_List** Head,

Double_List* Prior){

if (n > 0) {

(*Head) = new Double_List();

//выделяем память под новый элемент

cout << "Введите значение ";

cin >> (*Head)->Data;

//вводим значение информационного поля

(*Head)->Prior = Prior;

(*Head)->Next=NULL;//обнуление адресного поля

Make_Double_List(n-1,&((*Head)->Next),(*Head));

}

else (*Head) = NULL;

}

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

//печать двунаправленного списка

void Print_Double_List(Double_List* Head) {

if (Head!= NULL) {

cout << Head->Data << "\t";

Print_Double_List(Head->Next);

//переход к следующему элементу

}

else cout << "\n";

}

В динамические структуры легко добавлять элементы, так как для этого достаточно изменить значения адресных полей. Операция вставки реализовывается аналогично функции вставки для однонаправленного списка, только с учетом особенностей двунаправленного списка (рис. 5).

Рис. 5. Добавление элемента в двунаправленный список

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

Double_List* Insert_Item_Double_List(Double_List* Head,

int Number, int DataItem){

Number--;

Double_List *NewItem=new(Double_List);

NewItem->Data=DataItem;

NewItem->Prior=NULL;

NewItem->Next = NULL;

if (Head == NULL) {//список пуст

Head = NewItem;

}

else {//список не пуст

Double_List *Current=Head;

for(int i=1; i < Number && Current->Next!=NULL; i++)

Current=Current->Next;

if (Number == 0){

//вставляем новый элемент на первое место

NewItem->Next = Head;

Head->Prior = NewItem;

Head = NewItem;

}

else {//вставляем новый элемент на непервое место

if (Current->Next!= NULL) Current->Next->Prior = NewItem;

NewItem->Next = Current->Next;

Current->Next = NewItem;

NewItem->Prior = Current;

Current = NewItem;

}

}

return Head;

}

Дата добавления: 2014-01-04