Для доступа к требуемому элементу линейного списка необходимо просматривать список с его начала независимо от положения исходной точки просмотра. Это замедляет операции доступа к элементам в списке. Замыкание элементов списка в кольцо позволяет устранить этот недостаток. Такой список называется циклическим. Просмотр циклического списка можно начинать с любого элемента, а не только с его начала, причем началом списка может служить любой из его элементов. Логическая структура циклического списка:

1. Операции над циклическим списком

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

Для циклического списка также вводится новая операция – сцепление двух циклических списков – Сoncat (с 1,с 2).

1. Односвязная реализация циклического списка

Реализация циклического списка с помощью динамических переменных:

Такой список называется односвязным циклическим списком . Из любого элемента списка можно достичь любого другого элемента. Отметим, что циклический список не имеет первого и последнего элементов. Внешний указательHeadудобно использовать в качестве указателя на текущий элемент списка. При решении конкретных задач условно можно считать, что он адресуетпоследний элемент списка, что автоматически делает следующий за ним элемент первым.

Класс tCircleListможет быть описан следующим образом:

tValue= Real;// тип значения элемента списка - вещественный

pItem= ^tItem; // тип указателя на элемент списка

tItem= record // тип элемента списка

Value: tValue; // содержательная часть элемента списка

Next: pItem; // указатель на следующий элемент списка

end ; // record tItem

tCircleList=class // класс - циклический список

protected

fHead: pItem;// поле - указатель на текущий элемент списка

fSize:Word;// поле - число элементов списка

public

// Свойство - число элементов списка (доступ по чтению и записи)

property Size: Word read fSize write fSize;

// Свойство – указатель на начало списка (доступ по чтению и записи)

property Head: Word read fHead write fHead;

v после элемента с адресом Addr

procedure InsertAfter(Addr: pItem; v: tValue);

// Включение элемента со значением v перед элементом с адресом Addr

procedure InsertBefore(Addr: pItem; v: tValue);

// Исключение элемента, следующего за элементом с адресом Addr

function DeleteAfter(Addr: pItem): tValue;

// Исключение элемента с указателем Addr

function Delete(Addr:pItem):tValue;

// Включение элемента со значением v в начало списка

procedure InsertHead(v:tValue);

// Включение элемента со значением v в конец списка

procedure InsertRear(v:tValue);

// Исключение элемента из начала списка

function DeleteHead:tValue;

// Исключение элемента из конца списка

function DeleteRear:tValue;

procedure Concat(var CList2: tCircleList); // сцепление со списком CList2

// Поиск в списке элемента со значением v и возвращение его адреса

function Search(v: tValue): pItem;

function Empty: Boolean; // возвращение true, если список пуст

procedure Clear; // очистка списка

constructor Create; // конструктор - создание пустого списка

destructor Destroy; override ; // деструктор - удаление списка

end ; // class tCircleList

Класс tCircleListне объявлен наследником классаtListпоскольку реализация практически всех его методов отличается от реализации одноимённых методов для нециклического списка. Отличия, в основном, заключаются в следующем:

– для операций InsertAfterиInsertBeforeпо-другому осуществляются включение элемента в пустой список и включение в начало и конец циклического списка;

– применение операции DeleteAfterдля циклического списка, состоящего из одного элемента, не должно приводить к исключению самого этого элемента;

– методы DeleteAfterиDeleteдолжны восстанавливать указатель на последний элемент циклического списка, если он исключается при выполнении этих операций;

– в методах SearchиClearпризнаком завершения просмотра циклического списка является достижение вспомогательным указателем того элемента, с которого начался просмотр.

И только конструктор Createи деструкторDestroyреализуются так же как и одноимённые методы классаtList.

Очевидно, что операции включения и исключения справа и слева от текущего элемента (InsertHead,InsertRear,DeleteHead,DeleteRear) выполняют те же действия, что и одноимённые операции для нециклического списка. Отличие заключается в том, что новые операции изменяют значение указателя на последний элемент циклического списка, если список расширился влево или вправо либо сузился слева или справа.

Аннотация: В лекции рассматриваются определения, способы объявления, инициализация и особенности использования при решении задач циклических списков, деков, красно-черных деревьев, приводятся примеры решения задач на обработку кольцевых списков, деков, красно-черных деревьев.

Цель лекции : изучить алгоритмы и приемы работы с динамическими структурами данных , научиться решать задачи с использованием динамических структур данных и алгоритмов работы с ними на языке C++.

Структурированные типы данных , такие, как массивы, множества , записи, представляют собой статические структуры, так как их размеры неизменны в течение всего времени выполнения программы. Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими, к ним относятся стеки, очереди, списки, деревья и другие. Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти и увеличивает время решения задач.

Используя структурные типы , указатели и динамические переменные , можно создавать разнообразные динамические структуры памяти. Особенности указателей в языке С++ позволяют строить динамические структуры памяти на основе статически объявленных переменных или на смеси статических и динамических переменных . Идея организации всех динамических структур одна и та же. Определяется некоторый структурный тип S , одно или несколько полей которого объявлены указателями на тот же или некоторый другой структурный тип . В программе объявляется переменная d типа S или переменная типа указатель на S в случае полностью динамического создания структуры. Имя этой переменной при выполнении программы используется как имя "корня" (родительское имя) динамической структуры. При выполнении программы по мере построения динамической структуры запрашиваются динамические переменные соответствующих типов и связываются ссылками, начиная с переменной d или первой динамической переменной , указатель на которую содержится в переменной d . Этот подход позволяет создать динамическую структуру с любой топологией.

Циклические (кольцевые) списки

Циклический (кольцевой) список – это структура данных , представляющая собой последовательность элементов, последний элемент которой содержит указатель на первый элемент списка , а первый (в случае двунаправленного списка) – на последний.

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

Циклические списки, так же как и линейные, бывают однонаправленными и двунаправленными .

Похож на линейный однонаправленный список , но его последний элемент содержит указатель , связывающий его с первым элементом ( рис. 32.1).

Для полного обхода такого списка достаточно иметь указатель на произвольный элемент, а не на первый, как в линейном однонаправленном списке. Понятие "первого" элемента здесь достаточно условно и не всегда требуется. Хотя иногда бывает полезно выделить некоторый элемент как "первый" путем установки на него специального указателя. Это требуется, например, для предотвращения "зацикливания" при просмотре списка.

Рис. 32.1.

Основные операции , осуществляемые с циклическим однонаправленным списком:

• создание списка;
• печать (просмотр) списка;
• вставка элемента в список;
• удаление элемента из списка;
• поиск элемента в списке;
• проверка пустоты списка;
• удаление списка.

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

Приведем функции перечисленных основных операций при работе с циклическим однонаправленным списком.

//создание циклического однонаправленного списка void Make_Circle_Single_List(int n, Circle_Single_List** Head,Circle_Single_List* Loop){ if (n > 0) { (*Head) = new Circle_Single_List(); //выделяем память под новый элемент if (Loop == NULL) Loop = (*Head); cout << "Введите значение "; cin >> (*Head)->Data; //вводим значение информационного поля (*Head)->Next=NULL;//обнуление адресного поля Make_Circle_Single_List(n-1,&((*Head)->Next),Loop); } else { (*Head) = Loop; } } //печать циклического однонаправленного списка void Print_Circle_Single_List(Circle_Single_List* Head) { Circle_Single_List* ptr=Head; //вспомогательный указатель do { cout << ptr->Data << "\t"; ptr=ptr-> << "\n"; } /*вставка элемента после заданного номера в циклический однонаправленный список*/ Circle_Single_List* Insert_Item_Circle_Single_List(Circle_Single_List* Head, int Number, int DataItem){ Circle_Single_List *Current = Head; //встали на первый элемент Circle_Single_List *NewItem = new(Circle_Single_List); //создали новый элемент NewItem->Data = DataItem; if (Head == NULL) {//список пуст NewItem->Next = NewItem; Head = NewItem; } else {//список не пуст for (int i = 1; i < Number; i++) Current = Current->Next; NewItem->Next = Current->Next; Current->Next = NewItem; } return Head; } /*удаление элемента с заданным номером из циклического однонаправленного списка*/ Circle_Single_List* Delete_Item_Circle_Single_List (Circle_Single_List* Head, int Number){ if (Head != NULL){ Circle_Single_List *Current = Head; if (Head-> < Number; i++) Current = Current->Next; Circle_Single_List *ptr = Head; while (ptr->Next != Current) ptr = ptr->Next; //непосредственное удаление элемента ptr->Next = Current->Next; if (Head = Current) Head = Current->Next; delete(Current); } else{ Head = NULL; delete(Current); } } return Head; } //поиск элемента в циклическом однонаправленном списке bool Find_Item_Circle_Single_List(Circle_Single_List* Head, int DataItem){ Circle_Single_List *ptr = Head; //вспомогательный указатель do { if (DataItem == ptr->Data) return true; else ptr = ptr->Next; } while (ptr != Head); return false; } //проверка пустоты циклического однонаправленного списка bool Empty_Circle_Single_List(Circle_Single_List* Head){ return (Head != NULL ? false: true); } //удаление циклического однонаправленного списка void Delete_Circle_Single_List(Circle_Single_List* Head){ if (Head != NULL){ Head = Delete_Item_Circle_Single_List(Head, 1); Delete_Circle_Single_List(Head); } } Листинг 1.

Похож на линейный двунаправленный список , но его любой элемент имеет два указателя, один из которых указывает на следующий элемент в списке, а второй указывает на предыдущий элемент ( рис. 32.2).

Рис. 32.2.

Основные операции , осуществляемые с циклическим двунаправленным списком:

• создание списка;
• печать (просмотр) списка;
• вставка элемента в список;
• удаление элемента из списка;
• поиск элемента в списке
• проверка пустоты списка;
• удаление списка.

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

Приведем функции перечисленных основных операций при работе с циклическим двунаправленным списком.

//создание циклического двунаправленного списка Circle_Double_List* Make_Circle_Double_List(int n, Circle_Double_List** Head,Circle_Double_List* Loop){ Circle_Double_List* ptr;//вспомогательный указатель if (n > 0) { (*Head) = new Circle_Double_List(); //выделяем память под новый элемент if (Loop == NULL) Loop = (*Head); cout << "Введите значение "; cin >> (*Head)->Data; //вводим значение информационного поля (*Head)->Next=NULL;//обнуление адресного поля ptr = Make_Circle_Double_List(n-1,&((*Head)->Next),Loop); if ((*Head)->Next != NULL) (*Head)->Next->Prior = (*Head); if ((*Head)->Prior == NULL) (*Head)->Prior = ptr; if (ptr == NULL) return *Head; else return ptr; } else { (*Head) = Loop; return NULL; } } //печать циклического двунаправленного списка void Print_Circle_Double_List(Circle_Double_List* Head) { Circle_Double_List* ptr=Head; //вспомогательный указатель do { cout << ptr->Data << "\t"; ptr=ptr->Next; } while (ptr!=Head); cout << "\n"; } /*вставка элемента после заданного номера в циклический двунаправленный список*/ Circle_Double_List* Insert_Item_Circle_Double_List (Circle_Double_List* Head, int Number, int DataItem){ Circle_Double_List *Current = Head; //встали на первый элемент Circle_Double_List *NewItem = new(Circle_Double_List); //создали новый элемент NewItem->Data = DataItem; if (Head == NULL) {//список пуст NewItem->Next = NewItem; NewItem->Prior = NewItem; Head = NewItem; } else {//список не пуст for (int i = 1; i < Number; i++) Current = Current->Next; NewItem->Next = Current->Next; Current->Next = NewItem; NewItem->Prior = Current; NewItem->Next->Prior = NewItem; } return Head; } /*удаление элемента с заданным номером из циклического двунаправленного списка*/ Circle_Double_List* Delete_Item_Circle_Double_List(Circle_Double_List* Head, int Number){ if (Head != NULL){ Circle_Double_List *Current = Head; if (Head->Next != Head){ for (int i = 1; i < Number; i++) Current = Current->Next; Circle_Double_List *ptr = Current->Next; Current->Prior->Next = Current->Next; Current->Next->Prior = Current->Prior; if (Head = Current) //удаляем первый Head = Current->Next; delete(Current); } else{ Head = NULL; delete(Current); } } return Head; } //поиск элемента в циклическом двунаправленном списке bool Find_Item_Circle_Double_List(Circle_Double_List* Head, int DataItem){ Circle_Double_List *ptr = Head; //вспомогательный указатель do { if (DataItem == ptr->Data) return true; else ptr = ptr->Next; } while (ptr != Head); return false; } //проверка пустоты циклического двунаправленного списка bool Empty_Circle_Double_List(Circle_Double_List* Head){ return (Head != NULL ? false: true); } //удаление циклического двунаправленного списка void Delete_Circle_Double_List(Circle_Double_List* Head){ if (Head != NULL){ Head = Delete_Item_Circle_Double_List(Head, 1); Delete_Circle_Double_List(Head); } } Листинг 2.

Каждый узел однонаправленного (односвязного) циклического списка (ОЦС) содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит адрес корневого элемента.

Узел ОЦС можно представить в виде структуры, аналогичной односвязному линейному списку

struct list
{
int field; // поле данных
struct list *ptr; // указатель на следующий элемент
};

Основные действия, производимые над элементами ОЦС:

• Инициализация списка
• Добавление узла в список
• Удаление узла из списка
• Вывод элементов списка
• Взаимообмен двух узлов списка

Поскольку список является циклическим, реализация отдельной функции для удаления корня списка не требуется.

Инициализация списка предназначена для создания корневого узла списка, у которого поле указателя на следующий элемент содержит адрес самого корневого элемента.

1
2
3
4
5
6
7
8
9

struct list * init(int a) // а- значение первого узла
{
struct list *lst;
// выделение памяти под корень списка
lst = (struct list*)malloc(sizeof (struct list));
lst->field = a;
lst->ptr = lst; // указатель на сам корневой узел
return (lst);
}

Добавление узла в ОЦС

Функция добавления узла в список принимает два аргумента:

• Указатель на элемент, после которого происходит добавление
• Данные для добавляемого элемента.

Процедуру добавления элемента можно отобразить следующей схемой:


Добавление элемента в ОЦС включает в себя следующие этапы:

• создание добавляемого узла и заполнение его поля данных;
• переустановка указателя узла, предшествующего добавляемому, на добавляемый узел;
• установка указателя добавляемого узла на следующий узел (тот, на который указывал предшествующий узел).

Таким образом, функция добавления узла в ОЦС имеет вид, полностью аналогичный функции добавления узла в односвязный линейный список :

1
2
3
4
5
6
7
8
9
10

struct list * addelem(list *lst, int number)
{
struct list *temp, *p;
temp = (struct list*)malloc(sizeof (list));
p = lst->ptr; // сохранение указателя на следующий элемент
lst->ptr = temp; // предыдущий узел указывает на создаваемый
temp->field = number; // сохранение поля данных добавляемого узла
temp->ptr = p; // созданный узел указывает на следующий элемент
return (temp);
}

Возвращаемым значением функции является адрес добавленного узла.

Удаление узла ОЦС

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

Функция возвращает указатель на узел, следующий за удаляемым.

Удаление узла может быть представлено следующей схемой:

Удаление узла ОЦС включает в себя следующие этапы:

• установка указателя предыдущего узла на узел, следующий за удаляемым;
• освобождение памяти удаляемого узла.

1
2
3
4
5
6
7
8
9
10
11
12

struct list * deletelem(list *lst)
{
struct list *temp;
temp = lst;
while (temp->ptr != lst) // просматриваем список начиная с корня
{ // пока не найдем узел, предшествующий lst
temp = temp->ptr;
}
temp->ptr = lst->ptr; // переставляем указатель
free(lst); // освобождаем память удаляемого узла
return (temp);
}

Вывод элементов ОЦС

Функция вывода элементов ОЦС аналогична функции для ОЛС за исключением условия окончания обхода элементов.
В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.

1
2
3
4
5
6
7
8
9

void listprint(list *lst)
{
struct list *p;
p = lst;
do {
printf("%d " , p->field); // вывод значения узла p
p = p->ptr; // переход к следующему узлу
} while (p != lst); // условие окончания обхода
}

Для ОЦС также можно вызвать функцию вывода элементов списка начиная с любого узла.

Взаимообмен узлов ОЦС

В качестве аргументов функция взаимообмена ОЦС принимает два указателя за обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого узла списка.

Взаимообмен узлов списка осуществляется путем переустановки указателей. Для этого необходимо определить предшествующий и последующий узлы для каждого заменяемого. При этом возможны две ситуации:

• заменяемые узлы являются соседями;
• заменяемые узлы не являются соседями, то есть между ними имеется хотя бы один элемент.

При замене соседних узлов переустановка указателей выглядит следующим образом:


При замене узлов, не являющихся соседними переустановка указателей выглядит следующим образом:

При переустановке указателей необходимость в проверке корневого узла отсутствует (в отличие от аналогичной функции для lst2->ptr = lst1;
lst1->ptr = next2;
prev1->ptr = lst2;
}
else if (lst1 == next2)
{
// обмениваются соседние узлы
lst1->ptr = lst2;
lst2->ptr = next1;
prev2->ptr = lst2;
}
else
{
// обмениваются отстоящие узлы
prev1->ptr = lst2;
lst2->ptr = next1;
prev2->ptr = lst1;
lst1->ptr = next2;
}
if (lst1 == head)
return (lst2);
if (lst2 == head)
return (lst1);
return (head);
}

Текст лекции.

Структурированные типы данных, такие, как массивы, множества, записи, представляют собой статические структуры, так как их размеры неизменны в течение всего времени выполнения программы. Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими, к ним относятся стеки, очереди, списки, деревья и другие. Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти и увеличивает время решения задач.

Используя структурные типы, указатели и динамические переменные, можно создавать разнообразные динамические структуры памяти. Особенности указателей в языке С++ позволяют строить динамические структуры памяти на основе статически объявленных переменных или на смеси статических и динамических переменных. Идея организации всех динамических структур одна и та же. Определяется некоторый структурный тип S, одно или несколько полей которого объявлены указателями на тот же или некоторый другой структурный тип. В программе объявляется переменная d типа S или переменная типа указатель на S в случае полностью динамического создания структуры. Имя этой переменной при выполнении программы используется как имя «корня» (родительское имя) динамической структуры. При выполнении программы по мере построения динамической структуры запрашиваются динамические переменные соответствующих типов и связываются ссылками, начиная с переменной d или первой динамической переменной, указатель на которую содержится в переменной d. Этот подход позволяет создать динамическую структуру с любой топологией.

Циклический (кольцевой) список – это структура данных, представляющая собой последовательность элементов, последний элемент которой содержит указатель на первый элемент списка, а первый (в случае двунаправленного списка) – на последний.

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

Циклические списки, так же как и линейные, бывают однонаправленными и двунаправленными.

Циклический однонаправленный список похож на линейный однонаправленный список, но его последний элемент содержит указатель, связывающий его с первым элементом (рис. 1).

Для полного обхода такого списка достаточно иметь указатель на произвольный элемент, а не на первый, как в линейном однонаправленном списке. Понятие «первого» элемента здесь достаточно условно и не всегда требуется. Хотя иногда бывает полезно выделить некоторый элемент как «первый» путем установки на него специального указателя. Это требуется, например, для предотвращения «зацикливания» при просмотре списка.

Рис. 1. Циклический однонаправленный список

Основные операции, осуществляемые с циклическим однонаправленным списком:

· создание списка;

· печать (просмотр) списка;

· вставка элемента в список;

· поиск элемента в списке;

· проверка пустоты списка;

· удаление списка.

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

Приведем функции перечисленных основных операций при работе с циклическим однонаправленным списком.

//создание циклического однонаправленного списка

void Make_Circle_Single_List(int n,

Circle_Single_List** Head,Circle_Single_List* Loop){

(*Head) = new Circle_Single_List();

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

cin >> (*Head)->Data;

(*Head)->

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

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

void Print_Circle_Single_List(Circle_Single_List* Head) {

Circle_Single_List* ptr=Head;

//вспомогательный указатель

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

ptr=ptr->Next;

} while (ptr!=Head);

cout << "\n";

/*вставка элемента после заданного номера в циклический однонаправленный список*/

Circle_Single_List* Insert_Item_Circle_Single_List(Circle_Single_List* Head,

int Number, int DataItem){

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

Circle_Single_List *NewItem = new(Circle_Single_List);

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

NewItem->Data = DataItem;

NewItem->Next = NewItem;

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

for (int i = 1; i < Number; i++)

Current = Current->Next;

NewItem->Next = Current->Next;

Current->Next = NewItem;

/*удаление элемента с заданным номером из циклического однонаправленного списка*/

Circle_Single_List* Delete_Item_Circle_Single_List

(Circle_Single_List* Head, int Number){

if (Head != NULL){

Circle_Single_List *Current = Head;

if (Head->Next != Head){

for (int i = 1; i < Number; i++)

Current = Current->Next;

while (ptr->Next != Current)

ptr = ptr->Next;

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

ptr->Next = Current->Next;

if (Head = Current) Head = Current->Next;

delete(Current);

delete(Current);

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

bool Find_Item_Circle_Single_List(Circle_Single_List* Head,

Circle_Single_List *ptr = Head;

//вспомогательный указатель

if (DataItem == ptr->Data) return true;

else ptr = ptr->Next;

while (ptr != Head);

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

bool Empty_Circle_Single_List(Circle_Single_List* Head){

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

void Delete_Circle_Single_List(Circle_Single_List* Head){

if (Head != NULL){

Head = Delete_Item_Circle_Single_List(Head, 1);

Delete_Circle_Single_List(Head);

Циклический двунаправленный список похож на линейный двунаправленный список, но его любой элемент имеет два указателя, один из которых указывает на следующий элемент в списке, а второй указывает на предыдущий элемент (рис. 2).

Рис.2. Циклический двунаправленный список

Основные операции, осуществляемые с циклическим двунаправленным списком:

· создание списка;

· печать (просмотр) списка;

· вставка элемента в список;

· удаление элемента из списка;

· поиск элемента в списке

· проверка пустоты списка;

· удаление списка.

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

Приведем функции перечисленных основных операций при работе с циклическим двунаправленным списком.

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

Circle_Double_List* Make_Circle_Double_List(int n,

Circle_Double_List** Head,Circle_Double_List* Loop){

Circle_Double_List* ptr;//вспомогательный указатель

(*Head) = new Circle_Double_List();

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

if (Loop == NULL) Loop = (*Head);

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

cin >> (*Head)->Data;

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

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

ptr = Make_Circle_Double_List(n-1,&((*Head)->Next),Loop);

if ((*Head)->Next != NULL)

(*Head)->Next->Prior = (*Head);

if ((*Head)->Prior == NULL)

(*Head)->Prior = ptr;

if (ptr == NULL)

else return ptr;

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

void Print_Circle_Double_List(Circle_Double_List* Head) {

Circle_Double_List* ptr=Head;

//вспомогательный указатель

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

ptr=ptr->Next;

} while (ptr!=Head);

cout << "\n";

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

Circle_Double_List* Insert_Item_Circle_Double_List

(Circle_Double_List* Head, int Number, int DataItem){

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

Circle_Double_List *NewItem = new(Circle_Double_List);

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

NewItem->Data = DataItem;

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

NewItem->Next = NewItem;

NewItem->Prior = NewItem;

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

for (int i = 1; i < Number; i++)

Current = Current->Next;

NewItem->Next = Current->Next;

Current->Next = NewItem;

NewItem->Prior = Current;

NewItem->Next->Prior = NewItem;

/*удаление элемента с заданным номером из циклического двунаправленного списка*/

Circle_Double_List* Delete_Item_Circle_Double_List(Circle_Double_List* Head,

if (Head != NULL){

Circle_Double_List *Current = Head;

if (Head->Next != Head){

for (int i = 1; i < Number; i++)

Current = Current->Next;

Circle_Double_List *ptr = Current->Next;

Current->Prior->Next = Current->Next;

Current->Next->Prior = Current->Prior;

if (Head = Current) //удаляем первый

Head = Current->Next;

delete(Current);

delete(Current);

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

bool Find_Item_Circle_Double_List(Circle_Double_List* Head,

Circle_Double_List *ptr = Head;

//вспомогательный указатель

if (DataItem == ptr->Data)

else ptr = ptr->Next;

while (ptr != Head);

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

bool Empty_Circle_Double_List(Circle_Double_List* Head){

return (Head != NULL ? false: true);

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

void Delete_Circle_Double_List(Circle_Double_List* Head){

if (Head != NULL){

Head = Delete_Item_Circle_Double_List(Head, 1);

Delete_Circle_Double_List(Head);